Morris Inorder Traversal - Naukri Code 360

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.

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.

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.

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:

Step 1: Initialize the current node as the root.

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.

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.

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.

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.

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.

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

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;
}

You can also try this code with Online C++ Compiler

Run Code

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);
    }
}

You can also try this code with Online Java Compiler

Run Code

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)

You can also try this code with Online Python Compiler

Run Code

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);

You can also try this code with Online Javascript Compiler

Run Code

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.