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 Preorder
4.
Understanding the Morris Traversal Preorder
4.1.
Algorithm 
4.2.
Pseudo Code 
5.
Time for an Example 
6.
Implementation
6.1.
C++
6.2.
Java
7.
Complexity Analysis 
7.1.
Time Complexity:
7.2.
Space Complexity:
8.
Frequently Asked Questions
8.1.
What is the major difference between Morris Inorder Traversal and Morris Preorder Traversal?
8.2.
Is Morris Preorder Traversal commonly used in practice?
8.3.
Are there any limitations to Morris Preorder Traversal?
9.
Conclusion
Last Updated: Mar 27, 2024
Medium

Morris Traversal Preorder

Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction 

Traversing data structures is indeed one of the core and fundamental operations in computer science and programming. It's a fundamental building block for many algorithms and is essential for various tasks and applications.. When 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. 

Morris Traversal Preorder

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 Preorder Algorithm.

So, let us start our journey: 

Understanding Tree Traversal 

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

So far we have discussed the traversals that are Iterative or Recursive. In the Iterative approach, we used Stack and in the recursive approach, the stack is implemented internally for maintaining the calls. 

While these approaches 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. So, we aim to achieve O(1) space complexity with the help of Morris Traversal Algorithm. 

Understanding the Morris Traversal Preorder

Morris Traversal Preorder is a variation of the Morris Traversal algorithm that allows you to traverse a binary tree in preorder (root-left-right) order without using additional memory structures like stacks. It uses the Morris Link technique to achieve this. The links which we will be generating between the nodes will be temporary, that means after successful traversal of the nodes, the changes are reverted back to restore the original tree. 

Algorithm 

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

1. Start at the root node.

2. While the current node is not null:

	2.1 If the current node has no left child: 
	
		2.1.1 Visit the current Node 
		       Make the right child as the current Node.
     
    2.2 Else:
    
     Find the rightmost (maximum) node in the left subtree (this is the predecessor of the current node). 

	2.2.1 If predecessor.right does not exist, 

		Make the predecessor.right = current. This will generate the temporary link between the current and the predecessor node. 
		Visit the current Node
		Next, make the current = current.left
		
    2.2.2 Else: 
        Do the predecessor.right = Null ( Remove the temporary link )
  		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
      visit(current)
      current = current.left

    else
      predecessor.right = Null
      current = current.right

Time for an Example 

Let us see one example to look at its working. 

We have the following binary tree: 

Binary Tree Example

Let us quickly find its preorder: 

The Preorder will be : 10 5 2 7 15 30

Let us try to find the same result using the Morris Traversal algorithm: 


Step 1: Make the root as the current node. 

Binary Tree Example

 

Step 2: Check if the current.left exists or not. In our case it does exist, so we will find the predecessor to the current Node(10). Make the predecessor.right = current.

Binary Tree Example

 

Step 3: The next step is to visit the Current Node (10). 

Binary Tree Example

 

Step 4: Update the Current to Current.left

Binary Tree Example

So far, one iteration is done. Let us move to the second iteration, as our Current is not null. 

Step 5: Again, we will check if Current.left exists or not. It again exists as you can see in the above diagram. Thus, we will find the predecessor again and will generate the temporary link to the current node. 

Binary Tree Example

Step 6: The next is to visit the current node ( 5 ). 

Morris Traversal Preorder

Step 7: In this step, we will be updating the Current node to its current.left. 

Morris Traversal Preorder

Now, we will move towards the third Iteration. 

 

Step 8: At this point, the current.left doesn’t exist anymore. Now, we will have to perform these rules: visit(current) and update the current with current.right. 

Morris Traversal Preorder

In the above image, you can see we have utilized the temporary link to update the current with the current.right. 

 

4th Iteration: 

 

Step 9: This is the interesting part. Now, at this point, the current.left does exist. So, we will find the predecessor. The predecessor will be 2. Now, if you check the condition: If predecessor.right doesn't exist then visit the current node. But, in this case, predecessor.right does exist. 

Morris Traversal Preorder

So, now we will be doing these operations: 

 

Do the predecessor.right = Null ( Remove the temporary link )

Make the current = current.right. 

 

Step 10: Remove the temporary link and update the current node with its current.right. 

Binary Tree Example

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

Implementation

  • 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 morrisPreorderTraversal(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;

std::cout << current->val << " "; // Visit the current node.

current = current->left;

} else {

// Revert the change made in the previous step.

predecessor->right = nullptr;

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 Preorder Traversal: ";

morrisPreorderTraversal(root);

return 0;

}

Java

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

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

class MorrisPreorderTraversal {
public static void morrisPreorderTraversal(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;
System.out.print(current.val + " "); // Visit the current node.
current = current.left;
} else {
// Revert the change made in the previous step.
predecessor.right = null;
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 Preorder Traversal: ");
morrisPreorderTraversal(root);
}
}

 

Output 

output of morris traversal implementaion

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 the major difference between Morris Inorder Traversal and Morris Preorder Traversal?

Morris Inorder Traversal visits nodes in the order of left-root-right, while Morris Preorder Traversal visits nodes in the order of root-left-right. The primary difference is the timing of when the current node is visited (in the leftward move for Morris Inorder and during the initial step for Morris Preorder).

Is Morris Preorder Traversal commonly used in practice?

While Morris Traversal techniques are elegant and memory-efficient, they are less commonly used in practice compared to traditional recursive or stack-based approaches. This is because they involve modifying the tree temporarily, which may not be desirable in certain scenarios.

Are there any limitations to Morris Preorder Traversal?

Morris Traversal techniques are not well-suited for multithreaded environments or concurrent access to the tree structure, as they involve modifying the tree. Additionally, they may be less intuitive and harder to debug compared to traditional traversal methods.

Conclusion

To summarise the discussion, we have extensively discussed the Morris Traversal Preorder. We have started with discussing the types of traversals followed by the need of the Morris Traversal. As we have seen that it eliminates the need of stack in the algorithm which is an elegant approach and undoubtedly memory efficient. Yet, this amazing algorithm is lesser known in the market but plays a crucial role in Interviews. 

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 enrol in our courses and check out the mock tests and problems available to you. Please check out our interview experiences and interview bundle for placement preparations.

Happy Coding!

Previous article
How to Count the Number of Nodes in a Complete Binary Tree
Next article
Find n-th node of the inorder traversal
Live masterclass