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.

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.

The {22} above refers to 22 and all of its children. Now that the tree has a link back to 44, the traversal continues.

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 COURSES
View all Courses