Year-End Discount: 10% OFF 1-year and 20% OFF 2-year subscriptions!

Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

tree
morris traversal

What is Morris traversal?

Educative Answers Team

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.

Algorithm

  • 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.

Demo

Let’s take the binary tree given below and traverse it using Morris (InOrder) traversal.

Binary tree

44 is the root, so it is initialized as curr. 44 has a left child, so it is made the rightmost right child of it’s left subtree (the immediate predecessor to 44 in an InOrder traversal). Finally, 44 is made the right child of 33 and curr is set to 22.

1st and the 2nd iterations

Now the curr is on 22 and has a left child and right child is already linked to root. So we move the curr to 11. curr has no left and right child. Right will be linked to the root 22

3rd and 4th iterations

11 is printed because it has no left child and curr is returned to 22, which was made to be 11's right child in the previous iteration. On the next iteration, 22 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 33. 33 prints itself, and curr becomes 33 and goes through the same checking process that 22 did. It also realizes that its left subtree has been traversed and continues with the 44. The rest of the tree follows this same pattern.

Code

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 its
previous */
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

tree
morris traversal

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. 💪

Keep Exploring
Related Courses