Visualize recursive call stacks, queue progressions, and constant space threaded Morris algorithms.
Each edge is traversed at most 3 times (finding predecessor, creating thread, removing thread). Thus, overall time remains O(N).
Extraordinary feature: Morris Traversal uses threaded binary trees to navigate without recursion stack or queues, achieving true constant auxiliary space!
morrisInOrder(root) {curr = root;
while (curr !== null) { if (curr.left === null) {visit(curr); curr = curr.right;
} else {pred = findPredecessor(curr);
if (pred.right === null) {pred.right = curr; // Create thread
curr = curr.left;
} else {pred.right = null; // Clear thread
visit(curr); curr = curr.right;
}
}
}
}