Explain Morris inorder tree traversal without using stacks or recursion

The recursive in-order traversal is : (in-order(left)->key->in-order(right)). (this is similar to DFS)

When we do the DFS, we need to know where to backtrack to (that's why we normally keep a stack).

As we go through a parent node to which we will need to backtrack to -> we find the node which we will need to backtrack from and update its link to the parent node.

When we backtrack? When we cannot go further. When we cannot go further? When no left child's present.

Where we backtrack to? Notice: to SUCCESSOR!

So, as we follow nodes along left-child path, set the predecessor at each step to point to the current node. This way, the predecessors will have links to successors (a link for backtracking).

We follow left while we can until we need to backtrack. When we need to backtrack, we print the current node and follow the right link to the successor.

If we have just backtracked -> we need to follow the right child (we are done with left child).

How to tell whether we have just backtracked? Get the predecessor of the current node and check if it has a right link (to this node). If it has - than we followed it. remove the link to restore the tree.

If there was no left link => we did not backtrack and should proceed following left children.

Here's my Java code (Sorry, it is not C++)

public static <T> List<T> traverse(Node<T> bstRoot) {
    Node<T> current = bstRoot;
    List<T> result = new ArrayList<>();
    Node<T> prev = null;
    while (current != null) {
        // 1. we backtracked here. follow the right link as we are done with left sub-tree (we do left, then right)
        if (weBacktrackedTo(current)) {
            assert prev != null;
            // 1.1 clean the backtracking link we created before
            prev.right = null;
            // 1.2 output this node's key (we backtrack from left -> we are finished with left sub-tree. we need to print this node and go to right sub-tree: inOrder(left)->key->inOrder(right)
            result.add(current.key);
            // 1.15 move to the right sub-tree (as we are done with left sub-tree).
            prev = current;
            current = current.right;
        }
        // 2. we are still tracking -> going deep in the left
        else {
            // 15. reached sink (the leftmost element in current subtree) and need to backtrack
            if (needToBacktrack(current)) {
                // 15.1 return the leftmost element as it's the current min
                result.add(current.key);
                // 15.2 backtrack:
                prev = current;
                current = current.right;
            }
            // 4. can go deeper -> go as deep as we can (this is like dfs!)
            else {
                // 4.1 set backtracking link for future use (this is one of parents)
                setBacktrackLinkTo(current);
                // 4.2 go deeper
                prev = current;
                current = current.left;
            }
        }
    }
    return result;
}

private static <T> void setBacktrackLinkTo(Node<T> current) {
    Node<T> predecessor = getPredecessor(current);
    if (predecessor == null) return;
    predecessor.right = current;
}

private static boolean needToBacktrack(Node current) {
    return current.left == null;
}

private static <T> boolean weBacktrackedTo(Node<T> current) {
    Node<T> predecessor = getPredecessor(current);
    if (predecessor == null) return false;
    return predecessor.right == current;
}

private static <T> Node<T> getPredecessor(Node<T> current) {
    // predecessor of current is the rightmost element in left sub-tree
    Node<T> result = current.left;
    if (result == null) return null;
    while(result.right != null
            // this check is for the case when we have already found the predecessor and set the successor of it to point to current (through right link)
            && result.right != current) {
        result = result.right;
    }
    return result;
}

If I am reading the algorithm right, this should be an example of how it works:

     X
   /   \
  Y     Z
 / \   / \
A   B C   D

First, X is the root, so it is initialized as current. X has a left child, so X is made the rightmost right child of X's left subtree -- the immediate predecessor to X in an inorder traversal. So X is made the right child of B, then current is set to Y. The tree now looks like this:

    Y
   / \
  A   B
       \
        X
       / \
     (Y)  Z
         / \
        C   D

(Y) above refers to Y and all of its children, which are omitted for recursion issues. The important part is listed anyway. Now that the tree has a link back to X, the traversal continues...

 A
  \
   Y
  / \
(A)  B
      \
       X
      / \
    (Y)  Z
        / \
       C   D

Then A is outputted, because it has no left child, and current is returned to Y, which was made A's right child in the previous iteration. On the next iteration, Y has both children. However, the dual-condition of the loop makes it stop when it reaches itself, which is an indication that it's left subtree has already been traversed. So, it prints itself, and continues with its right subtree, which is B.

B prints itself, and then current becomes X, which goes through the same checking process as Y did, also realizing that its left subtree has been traversed, continuing with the Z. The rest of the tree follows the same pattern.

No recursion is necessary, because instead of relying on backtracking through a stack, a link back to the root of the (sub)tree is moved to the point at which it would be accessed in a recursive inorder tree traversal algorithm anyway -- after its left subtree has finished.