Morris Traversal for Inorder

Introduction

We can traverse a binary tree without utilizing stack or recursion by using Morris Traversal. Morris Traversal is based on the Threaded Binary Tree concept.

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.

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.

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.

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

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

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)

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.

Morris traversal for Preorder

Morris Traversal for Preorder is a tree traversal algorithm that allows the traversal of a binary tree in pre-order sequence without using recursion or an explicit stack. It modifies the structure of the tree temporarily by creating additional links (threads) to navigate through the tree efficiently.

The basic idea of Morris Preorder Traversal is as follows:

1. Start at the root of the tree.

2. While the current node is not null:

a. Print the value of the current node.

b. If the left child is null, move to the right child.

c. If the left child is not null:

i. Find the rightmost node in the left subtree (the in-order predecessor).

ii. Make the right child of this rightmost node point to the current node.

iii. Move to the left child.

This process is repeated until all nodes in the tree are visited. The algorithm does not require a separate stack, making it an in-place and space-efficient approach for preorder traversal.

Algorithm of Morris traversal for Preorder

Here's a brief overview of the steps involved in Morris Preorder Traversal:

1. Initialize the current node as the root.

2. While the current node is not null:

a. If the left child is null:

i. Print the value of the current node.

ii. Move to the right child.

b. If the left child is not null:

i. Find the rightmost node in the left subtree.

ii. If the right child of this rightmost node is null:

• Make it point to the current node.
• Print the value of the current node.
• Move to the left child.

iii. If the right child is already the current node:

• Break the link (set it to null).
• Move to the right child.

This process continues until all nodes are visited in preorder sequence. The Morris Preorder Traversal achieves O(1) space complexity while maintaining a time complexity of O(n), where n is the number of nodes in the binary tree.

Implementation

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void morrisPreorder(TreeNode* root) {
    while (root) {
        if (!root->left) {
            cout << root->val << " ";
            root = root->right;
        } else {
            TreeNode* predecessor = root->left;
            while (predecessor->right && predecessor->right != root)
                predecessor = predecessor->right;

            if (!predecessor->right) {
                cout << root->val << " ";
                predecessor->right = root;
                root = root->left;
            } else {
                predecessor->right = nullptr;
                root = root->right;
            }
        }
    }
}

// Example usage:
int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    cout << "Morris Preorder Traversal: ";
    morrisPreorder(root);

    return 0;
}

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

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

public class MorrisPreorder {
    public static void morrisPreorder(TreeNode root) {
        while (root != null) {
            if (root.left == null) {
                System.out.print(root.val + " ");
                root = root.right;
            } else {
                TreeNode predecessor = root.left;
                while (predecessor.right != null && predecessor.right != root)
                    predecessor = predecessor.right;

                if (predecessor.right == null) {
                    System.out.print(root.val + " ");
                    predecessor.right = root;
                    root = root.left;
                } else {
                    predecessor.right = null;
                    root = root.right;
                }
            }
        }
    }

    // Example usage:
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        System.out.print("Morris Preorder Traversal: ");
        morrisPreorder(root);
    }
}

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def morris_preorder(root):
    while root:
        if not root.left:
            print(root.val, end=" ")
            root = root.right
        else:
            predecessor = root.left
            while predecessor.right and predecessor.right != root:
                predecessor = predecessor.right

            if not predecessor.right:
                print(root.val, end=" ")
                predecessor.right = root
                root = root.left
            else:
                predecessor.right = None
                root = root.right

# Example usage:
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

print("Morris Preorder Traversal:", end=" ")
morris_preorder(root)

class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = this.right = null;
    }
}

function morrisPreorder(root) {
    while (root) {
        if (!root.left) {
            console.log(root.val);
            root = root.right;
        } else {
            let predecessor = root.left;
            while (predecessor.right && predecessor.right !== root)
                predecessor = predecessor.right;

            if (!predecessor.right) {
                console.log(root.val);
                predecessor.right = root;
                root = root.left;
            } else {
                predecessor.right = null;
                root = root.right;
            }
        }
    }
}

// Example usage:
let root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

console.log("Morris Preorder Traversal:");
morrisPreorder(root);

Output:

Morris Preorder Traversal: 1 2 4 5 3 

Time Complexity: O(n) because each node is visited once, and the algorithm doesn't use any additional data structures to store information about the nodes.

Space Complexity: O(1) because the algorithm doesn't use any extra space proportional to the input size. It utilizes the existing structure of the tree and only requires a constant amount of extra space for temporary variables. 

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.

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:

• Level Order Traversal of Binary Tree
• Check if Inorder and Preorder Traversals are Valid Without Building the Tree
• Practise Problems

Recommended problems -

• Zig Zag Tree Traversal 
• Preorder Traversal

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!