New update is available. Click here to update.
Last Updated: Nov 18, 2023
Medium

# Morris Traversal for Inorder

Mehak Goel
3 upvotes

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

• 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 = Nonedef 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 Nodedef 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 Nodefunction 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

• C++
• Java
• Python
• Javascript

### C++

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

### Java

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

### Python

``class TreeNode:    def __init__(self, x):        self.val = x        self.left = None        self.right = Nonedef 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)``

### Javascript

``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:

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!