What is Morris traversal?
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
rootas the current nodecurr. -
While
curris notNULL, check ifcurrhas a left child. -
If
currdoes not have a left child, printcurrand update it to point to the node on the right ofcurr. -
Else, make
currthe right child of the rightmost node incurr's left subtree. -
Update
currto this left node.
Demo
Let’s take the binary tree given below and traverse it using Morris (InOrder) traversal.
is the root, so it is initialized as curr. has a left child, so it is made the rightmost right child of it’s left subtree (the immediate predecessor to in an InOrder traversal). Finally, is made the right child of and curr is set to .
Now the curr is on and has a left child and right child is already linked to root. So we move the curr to . curr has no left and right child. Right will be linked to the root
is printed because it has no left child and curr is returned to , which was made to be 's right child in the previous iteration. On the next iteration, 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 . prints itself, and curr becomes and goes through the same checking process that did. It also realizes that its left subtree has been traversed and continues with the . 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 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;}
Free Resources
