Can we perform inorder traversal on a binary tree without using recursion or a stack, while also keeping the space complexity constant?

This is where Morris traversal comes in.

We have seen inorder traversal of binary tree here - Binary Tree Traversal - Inorder. The iterative version involves stack. Now lets see Morris Traversal.

The idea of Morris Traversal is based on Threaded Binary Tree. This approach achieves inorder traversal by establishing temporary links within the tree itself. The data is then printed by following these links, and finally, the tree structure is restored to its original state.

Algorithm

  • At each step we will check if current node has:
    • No left child:
      • Update traversal: Add current node to traversal
      • Move Right: The current pointer is advanced to its right child.
    • has left child: then establish a temp link:
      • Find Rightmost in Left Subtree: It traverses the current node’s left subtree and locates the rightmost node.
      • Link Establishment: The rightmost node’s right child pointer is set to point back to the current node, essentially creating a temporary link.
      • Move Left: The current pointer is then moved to this left child, continuing the traversal process.

Although the tree is modified through the traversal, it is reverted back to its original shape after the completion. 

Dry Run

To summarize, we create threaded pointers (predecssors to root) when the left child exists, and then traverse left child. Once left children are processed, we process current child.

Code

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

public List<Integer> morrisInorderTraversal(TreeNode root) {
    if (root == null) {
        return;
    }

    TreeNode curr = root;
    TreeNode prev = null;
    List<Integer> inorder = new ArrayList<>();
    while (curr != null) {
        // if no left subtree - add curr to traversal and visit right subtree     
        if (cur.left == null) {
	        inorder.add(curr.val);
            curr = curr.right;
        } else {
            // else traverse left subtree and come back to current node
            // Find the predecessor of current node
            prev = curr.left;
            while (prev.right != null && prev.right != curr) {
                prev = prev.right;
            }

            // Make current node as right child of its inorder predecessor
            if (prev.right == null) {
                prev.right = curr;
                curr = curr.left;
            } else {
                // we traversed left subtree through threaded pointer and reached curr again
                // so revert the threaded pointer and
                // add current node to traversal listbefore traversing right subtree
                prev.right = null;
                inorder.add(curr.val);
                //now traverse right subtree
                curr = curr.right;
            }
        }
    }
    return inorder;
}

Time Complexity

  • Time Complexity : O(n) - We traverse through all nodes, and each vertex is processed once.
  • Space Complexity: O(1)