Morris Inorder Traversal

So one of the most fundamental data structures in trees are Binary Search Trees. But when we talk about Binary trees a lot of folks tend to get confused.

The difference btw BST and Binary trees is that in Binary search trees, every node to the left of a node has values less than that node's value and every node to the right of the node has values greater than that node's value. In a binary tree, this is not the case necessarily.

Morris inorder traversal is a traversal algorithm where inorder predecessors and successors are linked. Morris inorder traversal doesn't make use of stack or recursion.

Below is the code for Morris inorder traversal

/**
 * Class for binary tree
 * class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) {
 *      val = x;
 *      left=null;
 *      right=null;
 *     }
 * }
 */

void morrisInorderTraversal(TreeNode root) {
    TreeNode curr = root;
    while(curr!=null) {
        if(curr.left == null) {
            System.out.println(curr.val);
            curr = curr.right;
        }
        // find the inorder predecessor
        else {
            TreeNode temp = curr.left;
            // first condition is to traverse to right most node
            // second condition is to stop when we reach link node
            while(temp.right!=null && temp.right!=curr) {
                temp=temp.right;        
            }

            // create link to the successor node
            if(temp.right == null) {
                temp.right = curr;
                curr=curr.left;
            }

            // break the previously created link
            else if (temp.right == curr) {
                temp.right = null;
                System.out.println(curr.val);
                curr = curr.right;
            }
        }

    }
}

Benefits of Morris Inorder traversal:

1. We don't need stack to keep track of nodes as we traverse. The stack consumes additional memory, which is inefficient when we have to traverse deep or large trees.

2. Cache friendly properties

3. In-place tree modification. Morris allows one to traverse and adjust link pointers in place

4. No Function call overhead due to recursion.

Cons:

1. May not be feasible when you want to preserve the original binary tree.

Time Complexity

O(N)

Space Complexity

O(1)