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

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

1st and the 2nd iterations

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

3rd and 4th iterations

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

Learn in-demand tech skills in half the time

Copyright Â©2022 Educative, Inc. All rights reserved.