Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
2.
Understanding Tree Traversal 
3.
Need of the Morris Traversal 
4.
Understanding the Morris Traversal 
4.1.
Algorithm 
4.2.
Pseudo Code 
4.3.
C++
4.4.
Java
5.
Complexity Analysis 
5.1.
Time Complexity:
5.2.
Space Complexity:
6.
Frequently Asked Questions
6.1.
What is traversing in data structure?
6.2.
What are the names of techniques for traversing a tree?
6.3.
What is the difference between traversing and searching?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

Morris Traversal

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction 

​​Traversing in data structures is an important aspect when dealing with different data structures. If we talk about tree traversal, then as the name suggests, it is the process of visiting all the nodes of a tree in a specific order. 

You must have heard about In Order, Preorder, Postorder and Level Order Traversal. But in this article, we will be talking about one lesser known but elegant method for traversing binary trees, i.,e, Morris Traversal Algorithm

Morris traversal

We will deep dive into the Intuition being designing such algorithms. We will also see its complexity analysis followed by the frequently asked questions. 

So, let us start our journey: 

Understanding Tree Traversal 

Trees in Computer Science are data structures consisting of nodes, with each node potentially having one or more child nodes. Traversing a tree means visiting all of the nodes in a specific order. 

There are mainly three types of tree traversals:
 

  • Inorder Traversal: Visits nodes in ascending order for a binary search tree (BST). In other words, it visits the left subtree, then the current node, and finally the right subtree.
     
  • Preorder Traversal: Visits the current node before its child nodes. It starts from the root node and moves towards the leaves.
     
  • Postorder Traversal: Visits the current node after its child nodes. It starts from the leaves and moves towards the root.
     

Now, you must be wondering, when we have these traversals, why do we worry about the other one: Morris traversal

The answer to this question is because of the space/memory issue of these algos. All these algos often use recursion or stack to keep track of the nodes and their order of visitation. While these methods work well, they require additional memory space for maintaining the call stack or an explicit stack data structure. The Morris Traversal Algorithm aims to perform tree traversal without any extra memory usage, making it highly efficient in terms of space.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Need of the Morris Traversal 

Let us go through the Inorder Traversal once then we will compare the tradition Inorder traversal with the Morris Traversal. 

Let us take an example of a binary Tree: 

demo tree

If we try to traverse the tree in an Inorder fashion, then we will start with the left most node, followed by the root node and then the right node. This follows until we visit all the nodes as you can see in the below image. 

Traditional Inorder

To implement the above idea, we will need to go back which requires some sort of additional data structure like a stack for Iterative approach. This results in a high memory consumption which is not an optimal solution. We can also use Recursion which again internally follows the same idea. 

So, to overcome this, we need some sort of algorithm that reduces the space complexity while maintaining the performance as it is. 

Here, comes the Morris Traversal which is designed to resolve this issue. 

Now that you have understood the Intuition behind the Morris Traversal, let us quickly jump into its concept architecture. 

Understanding the Morris Traversal 

The idea behind the Morris Traversal is to create the temporary links between the nodes so that we have a way to come back. We are calling them temporary links as we are going to remove them once the traversal is done. 

Algorithm 

Here's how the Morris Traversal Algorithm works for an inorder traversal:
 

  1. Start at the root node.
  2. While the current node is not null:

    If the current node has no left child: 

=> visit the current Node 

=> make the right child as the current Node.

    Else:

Find the rightmost (maximum) node in the left subtree (this is the predecessor of the current node). We find the predecessor of the current by moving one step towards the left and then the rightmost node from the left. The rightmost node will be the predecessor of the current node

If predecessor.right doesnot exist, Make the predecessor.right = current. This will generate the temporary link between the current and the predecessor node. 
Next, make the current = current.left
 

Else: do the predecessor.right = Null
Visit the current Node
Make the current = current.right. 

Pseudo Code 

current = root
while current is not NULL:
  if not exists current.left:
       visit(current)
       current = current.right
  else
    predecessor = findPredecessor(current)


    if not exists predecessor.right
      predecessor.right = current
      current = current.left


    else
      predecessor.right = Null
      visit(current)
      current = current.right


Let us see one example to look at its working. 

demo tree

Step 1: Start with the Root Node, i.,e, make it the current Node. 

Binary tree

Step 2: The next step is to find whether the current.left exists or not. In our case, it does exist. The next move is to find the predecessor of the current node, i.,e, 10. 

demo tree

Step 3: If predecessor.right doesnot exist, Make the predecessor.right = current. Now we will make the temporary link between the predecessor and the current node. 

demo tree

Step 4: The next move is to update the current. Now current will become current.left. 

 demo tree

Step 5: This step contains again checking the previous conditions. We will check if our current has current.left or not. It does exist, we will quickly find its predecessor. 

In this case, the right node doesn’t exist, so the predecessor will be 2 itself. Now, again we will generate the link between 2 and the 5(current node at the moment). 

Morris traversal

Step 6: The next step is again updating the current node to its current.left. 

Morris traversal

Step 7: Now comes the interesting part, we don’t have now current.left so we will now visit the current node ( 2) and update the current node again by its current.right. So, the current.right is 5. It is due to the link we have created just now. 

Morris traversal

Step 8: At this moment, the current node is 5 which again has a current.left. So, we will again find the predecessor of the current node. In this case, predecessor.right does exist. That means, we have already covered this cycle. 

So, we will follow these rules: 

Else: do the predecessor.right = Null 
Visit the current Node
Make the current = current.right. 


We will break the link and visit the current node and update the current node as current.right. In our case, the current node will now become 7. 

Morris traversal

The same steps will be followed until the current node becomes null. The final result will be the Inorder traversal of the binary tree. 

Let us now see its Implementation in different languages: 

  • C++
  • Java

C++

#include <iostream>

// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void morrisInorderTraversal(TreeNode* root) {
TreeNode* current = root;

while (current != nullptr) {
if (current->left == nullptr) {
// If the current node has no left child, visit it and move to the right.
std::cout << current->val << " ";
current = current->right;
} else {
// Find the rightmost node in the left subtree (predecessor).
TreeNode* predecessor = current->left;
while (predecessor->right != nullptr && predecessor->right != current) {
predecessor = predecessor->right;
}

if (predecessor->right == nullptr) {
// Make the current node the right child of its predecessor.
predecessor->right = current;
current = current->left;
} else {
// Revert the change made in the previous step.
predecessor->right = nullptr;
std::cout << current->val << " "; // Visit the current node.
current = current->right;
}
}
}
}

int main() {
// Create a sample binary tree.
TreeNode* root = new TreeNode(10);
root->left = new TreeNode(5);
root->right = new TreeNode(15);
root->left->left = new TreeNode(2);
root->left->right = new TreeNode(7);
root->right->right = new TreeNode(30);

std::cout << "Morris Inorder Traversal: ";
morrisInorderTraversal(root);

// Clean up memory (not shown in the example).

return 0;
}

Java

class TreeNode {
int val;
TreeNode left;
TreeNode right;

public TreeNode(int x) {
val = x;
left = null;
right = null;
}
}

class morrisInorderTraversal {
public static void morrisInorderTraversal(TreeNode root) {
TreeNode current = root;

while (current != null) {
if (current.left == null) {
// If the current node has no left child, visit it and move to the right.
System.out.print(current.val + " ");
current = current.right;
} else {
// Find the rightmost node in the left subtree (predecessor).
TreeNode predecessor = current.left;

while (predecessor.right != null && predecessor.right != current) {
predecessor = predecessor.right;
}

if (predecessor.right == null) {
// Make the current node the right child of its predecessor.
predecessor.right = current;
current = current.left;
} else {
// Revert the change made in the previous step.
predecessor.right = null;
System.out.print(current.val + " "); // Visit the current node.
current = current.right;
}
}
}
}

public static void main(String[] args) {
// Create a sample binary tree.
TreeNode root = new TreeNode(10);
root.left = new TreeNode(5);
root.right = new TreeNode(15);
root.left.left = new TreeNode(2);
root.left.right = new TreeNode(7);
root.right.right = new TreeNode(30);

System.out.print("Morris Inorder Traversal: ");
morrisInorderTraversal(root);
}
}

Output 

Morris traversal

Complexity Analysis 

Here is the breakdown of the complexity analysis of Morris Traversal: 

Time Complexity:

The time complexity of the Morris Traversal algorithm is O(n), where 'n' is the number of nodes in the binary tree. 

This complexity analysis is based on the fact that each node is visited exactly twice: once when establishing the Morris links (in the worst case) and once when traversing the tree.

Space Complexity:

The Morris Traversal algorithm is renowned for its space efficiency because it uses only a constant amount of extra space, making it an in-place traversal method. 

The space complexity is O(1), indicating that the amount of memory used by the algorithm is not dependent on the size of the input tree.

Frequently Asked Questions

What is traversing in data structure?

Traversing in data structure means iterating over each data structure element systematically to access them.

What are the names of techniques for traversing a tree?

The four main techniques for traversing a tree are level order, inorder, preorder, and postorder traversal.

What is the difference between traversing and searching?

In traversing, we are iterating over all the elements in the data structure at least once. In searching, we iterate through the data structure to find the particular element(s).

Conclusion

The Morris Traversal Algorithm is a clever and memory-efficient way to traverse binary trees. It uses the tree's own structure to achieve efficient traversal without additional memory overhead. While it may not be as widely known as other traversal techniques, understanding this algorithm can be valuable for situations where memory is limited or when you want to perform in-order tree traversal efficiently.

We have more for you. Give a read to the following articles to learn more about Traversals:

We hope this blog has helped you enhance your traversing in data structures knowledge. To learn more about DSA, competitive coding, and many more knowledgeable topics, please look into the guided paths on Coding Ninjas Studio. Also, you can enroll in our courses and check out the mock test and problems available to you. Please check out our interview experiences and interview bundle for placement preparations.

Happy Coding!

Previous article
Level Order Traversal Of  A Binary Tree
Next article
Level Order Traversal in Spiral Form
Live masterclass