94 · Binary Tree Inorder Traversal — Morris, O(1) space

In-order traversal without a stack and without recursion — by temporarily turning the tree's own unused right-child pointers into a way back up, then removing every trace of the detour before moving on.

1 — The problem, and the idea that makes O(1) possible

Return every value in ascending in-order sequence. The stack-based version (see 173 for the same stack mechanics applied to an iterator) is O(h) space for the call stack or an explicit Deque. Morris traversal gets this down to true O(1) auxiliary space — no stack, no recursion — by noticing that every node with a left child has a free right-child pointer sitting unused somewhere in that left subtree, on whichever node would be visited immediately before the current one finishes.

That free pointer belongs to the current node's inorder predecessor: the rightmost node in its left subtree. Point the predecessor's (currently null) right child back at the current node, and you've built a temporary thread — a way to return to exactly where you left off, without a stack remembering it for you. Once the thread has done its job, remove it. The tree looks completely untouched afterward.

2 — Visualizing the threading

Every dashed line in the diagram below is a temporary thread — an edge that doesn't exist in the real tree, created for exactly as long as it's needed and then removed. Solid lines are the tree's real edges, unchanged throughout.

List<Integer> result = new ArrayList<>();TreeNode cur = root;while (cur != null) {    if (cur.left == null) {        result.add(cur.val);        cur = cur.right;    } else {        TreeNode pred = cur.left;        while (pred.right != null && pred.right != cur) pred = pred.right;        if (pred.right == null) {            pred.right = cur; // thread            cur = cur.left;        } else {            pred.right = null; // unthread            result.add(cur.val);            cur = cur.right;        }    }}

Every node with a left child is visited by cur twice — once on the way down, when the thread gets created and the walk descends left instead of visiting; once on the way back up via that very thread, when it gets removed and the node is finally added to the result. A leaf, or any node with no left child, is visited only once, directly. Watch node 4, the root: its predecessor is 3, the rightmost node in its left subtree — the thread 3 → 4 is exactly how the walk climbs back out of the left subtree once it's exhausted.

3 — Complexity and edge cases

• Time: O(n), not immediately obvious — the inner while that hunts for the predecessor looks like it could make this O(n²), since it re-walks part of the left subtree. It doesn't: every edge in the tree is traversed at most twice total across the entire run — once to create a thread, once to find it again and remove it — so the total work is still linear.
• Space: O(1) auxiliary — the entire point of the technique. The tree itself is mutated temporarily, which is the trade-off: this isn't safe on a tree another thread might read concurrently, or one you need to guarantee is unchanged if the traversal is interrupted partway (an exception between threading and unthreading would leave a stray pointer behind).
• A tree that's just a right-leaning chain (no left children anywhere) never threads at all — it degenerates to the trivial cur = cur.right walk, visiting each node exactly once.
• Empty tree: the while (cur != null) guard exits immediately; empty result.

4 — Reference implementation

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    TreeNode cur = root;
    while (cur != null) {
        if (cur.left == null) {
            result.add(cur.val);
            cur = cur.right;
        } else {
            TreeNode pred = cur.left;
            while (pred.right != null && pred.right != cur) pred = pred.right;
            if (pred.right == null) {
                pred.right = cur;
                cur = cur.left;
            } else {
                pred.right = null;
                result.add(cur.val);
                cur = cur.right;
            }
        }
    }
    return result;
}