Morris Traversal (Inorder) | Inorder traversal of binary Tree without recursion and without using Stack

Morris traversal is a traversal technique which uses the concept of threaded binary tree and helps to traversal any binary tree without recursion and without using stack (any additional storage). In this article we discuss Morris Traversal for inorder binary tree traversal.
Submitted by Radib Kar, on August 04, 2020

Prerequisite:

In this article, we are going to see, how we can traverse inorder without using recursion and any additional storage with the help of converting the tree to a threaded binary Tree?

In a threaded binary tree we link up the leaf nodes to point to its inorder successor. The same idea is bought into Morris Traversal. Below is the algorithm for Morris traversal and then we have presented a pictorial representation to describe the traversal step by step.

Algorithm:

1)  Set current_node as root 
2)  While current_node is not NULL
        If the current_node does not have any left child
            Print/traverse the current_node
            Move to the right child and update 
            current_node = current_node ->right
        Else
            Mark the current_node as right child of its 
            inorder predecessor & move to the left child, 
            i.e., 
            update current = current->left. But, if it's already 
            made as right child of its inorder predecessor 
            (that means done in any previous iterations) 
            then delete that link (It restores the tree back), 
            print/traverse the current node(because the left subtree is traversed) 
            and move to its right child, 
            i.e., 
            update current = current->right      		
    End While

What is inorder predecessor?

Inorder predecessor is the node that comes just before the current node in the inorder traversal. Normally for a node, the inorder predecessor is the rightmost node is its left subtree, like for the below example:

5 is inorder predecessor of the root 1 as that's the rightmost node in the left subtree as shown below,

Figure 1: Inorder predecessor in a binary tree

Dry run with Example

The example tree is like below,

Figure 2: Original Binary Tree

Initially set current_node at root

Iteration 1:

So, the current node is 0.

Left child is not NULL, mark 0 as right child of its inorder predecessor (node 4) so go to left and update current_node= current_node->left for the next iteration.

Iteration 2:

So, the current Node is 1 now.

Left child is not NULL, mark 1 as right child of its inorder predecessor (node 3) and go to left and update current_node= current_node->left for the next iteration.

Iteration 3:

So, the current Node is 3

Left child is NULL

So, print/traverse the current node (It prints 3) and go to its right child. So, update current_node= current_node->right for the next iteration (see in the iteration 2 we set right child of 3 as 1).

Iteration 4:

So, the current Node is 1.

Left child is not NULL, and 1 is already marked as right child of its inorder predecessor(node 3). So delete this link and print 1 & go to right and update current_node= current_node->right for the next iteration.

Iteration 5:

So, the current Node is 4.

Left child is not NULL, so mark 4 as right child of its inorder predecessor (node 6) and go to left and update current_node= current_node->left for the next iteration 6.

Iteration 6:

So, the current Node is 6.

Left child is NULL

So, print/traverse the current node (It prints 6) and go to its right child. So, update current_node= current_node->right for next iteration (see in the previous iteration we set right child of 6 as 4).

Iteration 7:

So, the current Node is 4.

Left child is not NULL, and 4 is already marked as right child of its inorder predecessor (node 6). So delete this link and print 4 and go to right and update current_node= current_node->right for next iteration (check its right child has been linked with 0 previously).

Iteration 8:

So, the current Node is 10.

Left child is not NULL, and 10 is already marked as right child of its inorder predecessor (node 4). So, delete this link and print 10 and go to right and update current_node= current_node->right.

Iteration 9:

So, the current Node is 2.

Left child is NULL.

So, print/traverse the current node (It prints 2) and go to its right child. So, update current_node= current_node->right for next iteration no 10.

Iteration 10:

So, the current Node is 5.

Left child is NULL.

So, print/traverse the current node (It prints 5) and go to its right child. So, update current_node= current_node->right for next iteration.

Iteration 11:

Now the current node it NULL and thus it breaks the loop.

So, the overall traversal is:

3 1 6 4 0 2 5

3-> Got printed in iteration no 3
1-> Got printed in iteration no 4
6-> Got printed in iteration no 6
4-> Got printed in iteration no 7
0-> Got printed in iteration no 8
2-> Got printed in iteration no 9
5-> Got printed in iteration no 10

This is how Morris traversal works without recursion and without any extra storage. This has a time complexity of O(n) & a space complexity of O(1) , n be the number of nodes.

Below is the implementation for Morris inorder Traversal.

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int v)
    {
        val = v;
        left = NULL;
        right = NULL;
    }
};

void inorderTraversal(TreeNode* root)
{
    TreeNode* current_node = root;
    
    while (current_node) {
        //if it has left child
        if (current_node->left) { 
            /*
            link current node as right child of the 
            rightmost node in left subtree (inorder predecessor)
            if not done already
            */
            //find rightmost node in left subtree
            TreeNode* rightmost_in_left_subtree = current_node->left;
            while (rightmost_in_left_subtree->right && rightmost_in_left_subtree->right != current_node) {
                rightmost_in_left_subtree = rightmost_in_left_subtree->right;
            }

            //if current node is not linked as right child to 
            //its inorder predecessor then link it
            if (!rightmost_in_left_subtree->right) {
                rightmost_in_left_subtree->right = current_node;
                //move to left now
                current_node = current_node->left;
            }

            else {
                /*
                if alreday found linked in,
                then it means it has already been 
                linked in any previous traversal 
                and we have finished traversing the left subtree
                so traverse the current node and remove 
                the link to restore tree
                */
                cout << current_node->val << " "; //print
                rightmost_in_left_subtree->right = NULL; //removed the link

                //move to right now since left subtree 
                //has been traversed already
                current_node = current_node->right;
            }
        }
        else {
            //traverse the node and move to right child
            cout << current_node->val << " ";
            current_node = current_node->right;
        }
    }
}

int main()
{
    //Tree is built like the example
    TreeNode* root = new TreeNode(0);
    
    root->left = new TreeNode(1);
    root->right = new TreeNode(2);
    root->left->left = new TreeNode(3);
    root->left->right = new TreeNode(4);
    root->right->right = new TreeNode(5);
    root->left->right->left = new TreeNode(6);
    
    cout << "Inorder traversal using Morris traversal is:\n";
    
    inorderTraversal(root);
    
    return 0;
}

Output:

Inorder traversal using Morris traversal is:
3 1 6 4 0 2 5

Comments and Discussions!

Load comments ↻