Morris Traversal

Normal bst inorder traversal takes O(n) time, O(logn) space. Threaded bst inorder traversal takes O(n) time, O(1) space.

However, by Morris Traversal, we can traverse tree in O(n) time, O(1) space without constructing a threaded bst. Let me summary the rules for this algorithm.

1. If current node doesn’t has left child, then print current node. Like node 1, 3, 4, 8 etc.
   
2. If current node has left child,  then we check the right-most of left child.
   2. 1 If right child of right-most  is null, then point its right child to curr.
   
   2.2 If right child of right-most is not null, it means left child is already traversed. We need to set right child of right-most  to null.
   

This is my java code:

public static void morrisTraversal(TreeNode node) {
    TreeNode curr = node;
    while (curr != null) {
        if (curr.left == null) {    // if left is null, then print
            System.out.println(curr.val);
            curr = curr.right;
            continue;
        }
        TreeNode pre = curr.left;
        while (pre.right != null && pre.right != curr) {
            pre = pre.right;
        }
        if (pre.right == null) {
            pre.right = curr;
            curr = curr.left;
        }
        else {  // right end already points to curr, it means left is already traversed.
            pre.right = null;
            System.out.println(curr.val);
            curr = curr.right;
        }
    }   // while
}

Check my github.