How to use Morris Traversal In Javascript
Initializes variables – current pointing to the root, maxCount set to 0 for tracking maximum frequency, and modes as an empty array . It uses prev to track the previous node visited and count to monitor the frequency of the current value. While traversing, updates count and checks mode occurrences for null left child; otherwise, finds inorder predecessor for left child, adjusts pointers, and continues traversal. Returns the modes array after traversal completion.
Example: To demonstrate Finding the mode in a binary search tree using Morris Traversal
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
function findModeMorris(root) {
let current = root;
let maxCount = 0;
let modes = [];
let prev = null;
let count = 0;
while (current !== null) {
if (current.left === null) {
// Process current node
if (prev !== null
&&
prev.value === current.value) {
count++;
} else {
count = 1;
}
if (count > maxCount) {
maxCount = count;
modes = [current.value];
} else if (count === maxCount) {
modes.push(current.value);
}
prev = current;
current = current.right;
} else {
let predecessor = current.left;
while (
predecessor.right !== null
&&
predecessor.right !== current) {
predecessor = predecessor.right;
}
if (predecessor.right === null) {
predecessor.right = current;
current = current.left;
} else {
predecessor.right = null;
// Process current node
if (prev !== null && prev.value === current.value) {
count++;
} else {
count = 1;
}
if (count > maxCount) {
maxCount = count;
modes = [current.value];
} else if (count === maxCount) {
modes.push(current.value);
}
prev = current;
current = current.right;
}
}
}
return modes;
}
const root = new TreeNode(1);
root.right = new TreeNode(2);
root.right.left = new TreeNode(2);
console.log(findModeMorris(root));
Output
[ 2 ]
Time Complexity : O(n)
Space Complexity : O(1)
Find the Mode in a Binary Search Tree using JavaScript
One can find the mode in a binary search tree using JavaScript. The mode in the binary search tree will be the value of the node that occurs with the highest frequency among all the nodes in the tree. If there is more than one mode present in the binary search tree then return all modes present in the array.
There are several approaches to calculate mode in binary search tree using JavaScript which are as follows:
Table of Content
- Using Inorder Traversal & Hashmap
- Using Morris Traversal