Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is Morris traversal?
3.
What is Morris Traversal for Inorder?
4.
Algorithm of Morris traversal for Inorder
5.
Implementation
5.1.
C++
5.2.
Java
5.3.
Python
5.4.
Javascript
6.
Limitations of Morris Traversal
7.
Frequently Asked Questions
7.1.
What is Morris tree traversal?
7.2.
What is the difference between inorder traversal and Morris inorder traversal?
7.3.
What is the time complexity of Morris traversal algorithm?
7.4.
Why do we use Morris traversal?
7.5.
What is the Morris algorithm for tree traversal?
8.
Conclusion
Last Updated: May 16, 2024
Medium

Morris Traversal for Inorder

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

Introduction

Morris (InOrder) traversal is a tree traversal method that doesn't rely on recursion or a stack. Instead, it uses links to navigate through nodes, efficiently printing them as it moves along.

Morris Traversal

A threaded binary tree is just like a normal binary tree, but they have a specialty in which all the nodes whose right child pointers are NULL point to their in-order successor, and all the nodes whose left child pointers are NULL point to their in-order predecessor. It helps in facilitating faster tree traversal without requiring a stack or recursion.

threaded binary tree

What is Morris traversal?

Morris traversal is an in-order tree traversal algorithm for binary trees that uses threading. It allows in-order traversal of a binary tree without using recursion or an explicit stack, reducing the space complexity to O(1). Morris traversal modifies the tree temporarily by threading some of its nodes, making it a space-efficient alternative for in-order traversal.

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

What is Morris Traversal for Inorder?

Morris Traversal is a space-efficient algorithm for traversing binary trees in Inorder without using Recursion or a stack. It modifies the tree structure by adding temporary links between nodes to traverse the tree in a specific order. This approach reduces the space complexity to O(1) but increases the time complexity to O(n^2). It is not commonly used in practice due to its higher time complexity, but it can be useful in certain memory-constrained environments.

Algorithm of Morris traversal for Inorder

The Morris Traversal for Inorder is a type of tree traversal in which we first visit the left subtree then, the root node and in the end, the right subtree, which is the same as Inorder Traversal of the binary tree but without using stack or recursion.

Let us understand it using an example:

Consider the following Binary Tree:

Morris Traversal for Inorder

Step 1: Initialize the current node as the root.

current node

 

Step 2: While the current is not NULL, 

  • If the current node does not have a left child, print the current node’s value and update it to point to the right, i.e. current = current->right.
  • If the current node has a left child, then first connect the rightmost node of the left subtree to the root and then update the current node to point to the left, i.e. current = current-> left.
Morris Traversal tree

 

  • Update the right child as NULL of the node whose right child is node current and print the current’s value. Then move to right i.e., current = current->right.

OR

  • Make current as of the right child of that rightmost node we found and then go to this left child, i.e., current = current->left.
Traversal for Inorder

Step 3: Then, after printing the current node and traversing through it, we remove the threaded link, and the current node is updated to point to the right.

 

node and traversing

Step 4: After traversing all the nodes of the left subtree and printing the root node, we move to the right subtree by pointing the current node to the right.

 

printing the root node

Hence, After traversing through the whole binary tree, we have achieved our output. 

 

binary tree graph

Implementation

Let’s have a look at the Implementation of Morris Traversal for Inorder without using recursion and stack.

  • C++
  • Java
  • Python
  • Javascript

C++

#include <iostream>
using namespace std;


/* Node Structure in a threaded binary tree */
struct Node
{
int value;
struct Node *left;
struct Node *right;
};


/* Function to traverse the binary tree without using any additional space */
void Morris(struct Node *root)
{
struct Node *current, *prev;


if (root == NULL)
return;


current = root;
while (current != NULL)
{
if (current->left == NULL)
{
cout << current->value << "\t";
current = current->right;
}
else
{
/* Find the previous node of the current node */
prev = current->left;
while (prev->right != NULL && prev->right != current)
prev = prev->right;


/* Make current node as the right child of its previous node */
if (prev->right == NULL)
{
prev->right = current;
current = current->left;
}


/* fix the right child of previous */
else
{
prev->right = NULL;
cout << current->value << "\t";
current = current->right;
}
}
}
}


/* Function allocates a new Node with the given value and the left and right pointers to NULL. */


struct Node *add_node(int value)
{
struct Node *node = new Node;
node->value = value;
node->left = NULL;
node->right = NULL;

return (node);
}


int main()
{
struct Node *root = add_node(20);
root->left = add_node(40);
root->right = add_node(60);
root->left->left = add_node(80);
root->left->right = add_node(100);
Morris(root);
return 0;
}

Java

class Node {
int value;
Node left, right;

public Node(int item) {
value = item;
left = right = null;
}
}

public class MorrisTraversal {
static void morrisTraversal(Node root) {
Node current, prev;

if (root == null)
return;

current = root;
while (current != null) {
if (current.left == null) {
System.out.print(current.value + "\t");
current = current.right;
} else {
prev = current.left;
while (prev.right != null && prev.right != current)
prev = prev.right;

if (prev.right == null) {
prev.right = current;
current = current.left;
} else {
prev.right = null;
System.out.print(current.value + "\t");
current = current.right;
}
}
}
}

public static Node addNode(int value) {
return new Node(value);
}

public static void main(String[] args) {
Node root = addNode(20);
root.left = addNode(40);
root.right = addNode(60);
root.left.left = addNode(80);
root.left.right = addNode(100);

morrisTraversal(root);
}
}

Python

class Node:
def __init__(self, value):
self.value = value
self.left = self.right = None

def morris_traversal(root):
current, prev = None, None

if not root:
return

current = root
while current:
if not current.left:
print(current.value, end="\t")
current = current.right
else:
prev = current.left
while prev.right and prev.right != current:
prev = prev.right

if not prev.right:
prev.right = current
current = current.left
else:
prev.right = None
print(current.value, end="\t")
current = current.right

# Function to create a new Node
def add_node(value):
return Node(value)

# Example usage:
root = add_node(20)
root.left = add_node(40)
root.right = add_node(60)
root.left.left = add_node(80)
root.left.right = add_node(100)

morris_traversal(root)

Javascript

class Node {
constructor(value) {
this.value = value;
this.left = this.right = null;
}
}

function morrisTraversal(root) {
let current, prev;

if (!root)
return;

current = root;
while (current) {
if (!current.left) {
console.log(current.value + "\t");
current = current.right;
} else {
prev = current.left;
while (prev.right && prev.right !== current)
prev = prev.right;

if (!prev.right) {
prev.right = current;
current = current.left;
} else {
prev.right = null;
console.log(current.value + "\t");
current = current.right;
}
}
}
}

// Function to create a new Node
function addNode(value) {
return new Node(value);
}

// Example usage:
let root = addNode(20);
root.left = addNode(40);
root.right = addNode(60);
root.left.left = addNode(80);
root.left.right = addNode(100);

morrisTraversal(root);

Output

80  40 100  20  60

 

Time Complexity: O(n) as there are n number nodes in the binary tree, traversed through each node.

Space Complexity: O(1) as we are not using recursion or a stack.

Limitations of Morris Traversal

Morris traversal is a method of traversing a binary tree without using recursion or a stack, which reduces the space complexity to O(1). However, it has some limitations.

Firstly, it modifies the tree structure by creating temporary links, which may not be allowed in certain scenarios. For example, if the binary tree is read-only or shared by multiple threads, Morris traversal may not be suitable.

Secondly, it may not work well with certain types of binary trees, such as skewed trees, where one subtree is much larger than the other. In such cases, Morris traversal may result in an unbalanced traversal, leading to poor performance.

Finally, Morris traversal requires careful handling of edge cases, such as handling the root node and dealing with nodes with only one child. This may add complexity to the implementation and make it harder to debug.

Frequently Asked Questions

What is Morris tree traversal?

We can traverse the tree without using stack or recursion by using Morris Traversal. Morris Traversal is based on the Threaded Binary Tree concept. We build links to Inorder successors and display the data using these links in this traversal, then at the end reverse the changes to restore the original tree.

What is the difference between inorder traversal and Morris inorder traversal?

The main difference between inorder traversal and Morris inorder traversal is that Morris traversal uses constant space without a stack. 

What is the time complexity of Morris traversal algorithm?

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

Why do we use Morris traversal?

Morris traversal, an efficient and space-saving algorithm, is used for tree traversal when additional space for stack or recursion is not available. It achieves in-order traversal with constant space complexity.

What is the Morris algorithm for tree traversal?

The Morris algorithm enables in-order tree traversal without using recursion or an additional stack. It modifies the tree structure temporarily by threading the right pointers of certain nodes to their successors, allowing traversal without extra space overhead.

Conclusion

This article discussed the morris traversal for inorder in the C++ programming language. Morris Traversal uses the concept of Threaded Binary Trees, where the left null pointers are pointed to their inorder predecessors, and the null right pointers are pointed towards their inorder successors using threads. Hence, with the help of this, we got the inorder traversal of a binary tree without using a stack or recursion.  

Recommended Reading:

Recommended problems -

 

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Cheers!

Previous article
Diameter of Binary Tree
Next article
Sum of All the Parent Nodes Having Child Node X
Live masterclass