Tired of LeetCode? ðŸ˜©
Learn the 24 patterns to solve any coding interview question without getting lost in a maze of LeetCode-style practice problems. Practice your skills in a hands-on, setup-free coding environment. ðŸ’ª
Morris (InOrder) traversal is a tree traversal algorithm that does not employ the use of recursion or a stack. In this traversal, links are created as successors and nodes are printed using these links. Finally, the changes are reverted back to restore the original tree.
Initialize the root
as the current node curr
.
While curr
is not NULL
, check if curr
has a left child.
If curr
does not have a left child, print curr
and update it to point to the node on the right of curr
.
Else, make curr
the right child of the rightmost node in curr
's left subtree.
Update curr
to this left node.
Letâ€™s take the binary tree given below and traverse it using Morris (InOrder) traversal.
$4$ is the root, so it is initialized as curr
. $4$ has a left child, so it is made the rightmost right child of itâ€™s left subtree (the immediate predecessor to $4$ in an InOrder traversal). Finally, $4$ is made the right child of $3$ and curr
is set to $2$.
Now the curr
is on $2$ and has a left child and right child is already linked to root. So we move the curr
to $1$. curr
has no left and right child. Right will be linked to the root $2$
$1$ is printed because it has no left child and curr
is returned to $2$, which was made to be $1$'s right child in the previous iteration. On the next iteration, $2$ has both children. However, the dual-condition of the loop makes it stop when it reaches itself; this is an indication that its left subtree has already been traversed. So, it prints itself and continues with its right subtree $3$. $3$ prints itself, and curr
becomes $3$ and goes through the same checking process that $2$ did. It also realizes that its left subtree has been traversed and continues with the $4$. The rest of the tree follows this same pattern.
The above algorithm is implemented in the code below:
#include <iostream>using namespace std;struct Node {int data;struct Node* left_node;struct Node* right_node;};void Morris(struct Node* root){struct Node *curr, *prev;if (root == NULL)return;curr = root;while (curr != NULL) {if (curr->left_node == NULL) {cout << curr->data << endl;curr = curr->right_node;}else {/* Find the previous (prev) of curr */prev = curr->left_node;while (prev->right_node != NULL && prev->right_node != curr)prev = prev->right_node;/* Make curr as the right child of itsprevious */if (prev->right_node == NULL) {prev->right_node = curr;curr = curr->left_node;}/* fix the right child of previous */else {prev->right_node = NULL;cout << curr->data << endl;curr = curr->right_node;}}}}struct Node* add_node(int data){struct Node* node = new Node;node->data = data;node->left_node = NULL;node->right_node = NULL;return (node);}int main(){struct Node* root = add_node(4);root->left_node = add_node(2);root->right_node = add_node(5);root->left_node->left_node = add_node(1);root->left_node->right_node = add_node(3);Morris(root);return 0;}
RELATED TAGS
Tired of LeetCode? ðŸ˜©
Learn the 24 patterns to solve any coding interview question without getting lost in a maze of LeetCode-style practice problems. Practice your skills in a hands-on, setup-free coding environment. ðŸ’ª