a shot of dev knowledge

Related tags

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

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

## 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* node = new Node;
node->data = data;
node->left_node = NULL;
node->right_node = NULL;

return (node);
}

int main()
{

Morris(root);
return 0;
} 

Related tags

RELATED COURSES
Related Courses
Related Courses

#### Keep Exploring

Learn in-demand tech skills in half the time