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$.
The {$2$} above refers to $2$ and all of its children. Now that the tree has a link back to $4$, the traversal continues.
$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 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; }