Morris Traversal for Inorder

Mehak Goel
Last Updated: May 13, 2022

Introduction

We can traverse a binary tree without utilising 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 speciality 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.

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:

Source: Codespeedy

Step 1: Initialize the current node as the root.

Source: Codespeedy

 

Step 2: While 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.

Source: Codespeedy

 

  • Update the right child as NULL of the node whose right child is node current and print 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.

Source: Codespeedy

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.

 

Source: Codespeedy

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.

 

Source: Codespeedy

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

 

Source: Codespeedy

Code in C++

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

 

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.

Frequently Asked Questions

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


Q2. What is an Inorder predecessor?
In the inorder traversal of a binary tree, the predecessor is the node that we traversed before the given node. It's the previous node value before a node in a binary search tree.


Q3. Is Morris Traversal valid for preorder and postorder?
Yes, for traversing the tree in preorder and postorder, we can use the concept of morris traversal.  In Pre-Order Morris Traversal, we first visit the root node, left and right subtree. In Postorder, we first traverse the left subtree then, the right subtree, and in the end, the root node. This can also be achieved by reversing the Inorder Morris Traversal. 

Key Takeaways

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.  

Was this article helpful ?
1 upvote

Comments

No comments yet

Be the first to share what you think