The Morris algorithm achieves constant auxiliary space complexity by temporarily converting the binary tree into a threaded structure, utilizing null child pointers to establish return paths instead of explicit stacks or recursion.

Core Threading Mechanism

The fundamental operation involves locating the in-order predecessor (the rightmost node in the left subtree) to create a temporary link back to the current node. This allows downward traversal with a guaranteed path back up once the left subtree is exhausted.

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public void morrisTraversal(TreeNode root) {
    if (root == null) return;
    
    TreeNode current = root;
    while (current != null) {
        if (current.left != null) {
            TreeNode predecessor = current.left;
            while (predecessor.right != null && predecessor.right != current) {
                predecessor = predecessor.right;
            }
            
            if (predecessor.right == null) {
                predecessor.right = current;  // Create thread
                current = current.left;
                continue;
            } else {
                predecessor.right = null;     // Remove thread
            }
        }
        current = current.right;
    }
}

In-Order Traversal

Values are emitted when nodes are visited for the second time (during thread removal) or immediately for nodes without left children, yielding the classic left-root-right sequence.

public void morrisInOrder(TreeNode root) {
    if (root == null) return;
    
    TreeNode current = root;
    while (current != null) {
        if (current.left == null) {
            System.out.print(current.val + " ");
            current = current.right;
        } else {
            TreeNode predecessor = current.left;
            while (predecessor.right != null && predecessor.right != current) {
                predecessor = predecessor.right;
            }
            
            if (predecessor.right == null) {
                predecessor.right = current;
                current = current.left;
            } else {
                predecessor.right = null;
                System.out.print(current.val + " ");  // Visit on second arrival
                current = current.right;
            }
        }
    }
}

Pre-Order Traversal

For root-left-right ordering, nodes are processed during the initial encounter when establishing threads, or immediately when no left subtree exists.

public void morrisPreOrder(TreeNode root) {
    if (root == null) return;
    
    TreeNode current = root;
    while (current != null) {
        if (current.left == null) {
            System.out.print(current.val + " ");
            current = current.right;
        } else {
            TreeNode predecessor = current.left;
            while (predecessor.right != null && predecessor.right != current) {
                predecessor = predecessor.right;
            }
            
            if (predecessor.right == null) {
                System.out.print(current.val + " ");  // Visit before threading
                predecessor.right = current;
                current = current.left;
            } else {
                predecessor.right = null;
                current = current.right;
            }
        }
    }
}

Post-Order Traversal

Implementing left-right-root ordering requires printing the right boundary of each left subtree in reverse order upon the second visit to a node, followed by the root's right boundary at completion.

public void morrisPostOrder(TreeNode root) {
    if (root == null) return;
    
    TreeNode dummy = new TreeNode(0);
    dummy.left = root;
    TreeNode current = dummy;
    
    while (current != null) {
        if (current.left == null) {
            current = current.right;
        } else {
            TreeNode predecessor = current.left;
            while (predecessor.right != null && predecessor.right != current) {
                predecessor = predecessor.right;
            }
            
            if (predecessor.right == null) {
                predecessor.right = current;
                current = current.left;
            } else {
                predecessor.right = null;
                printReverse(current.left);
                current = current.right;
            }
        }
    }
}

private void printReverse(TreeNode node) {
    TreeNode tail = reverseChain(node);
    TreeNode iter = tail;
    while (iter != null) {
        System.out.print(iter.val + " ");
        iter = iter.right;
    }
    reverseChain(tail);
}

private TreeNode reverseChain(TreeNode head) {
    TreeNode prev = null;
    TreeNode curr = head;
    while (curr != null) {
        TreeNode next = curr.right;
        curr.right = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

BST Validation

A binary search tree property can be verified in O(1) space by ensuring the in-order sequence is strictly monotonically increasing durring the traversal.

public boolean isValidBST(TreeNode root) {
    if (root == null) return true;
    
    TreeNode current = root;
    Integer lastVisited = null;
    
    while (current != null) {
        if (current.left == null) {
            if (lastVisited != null && current.val <= lastVisited) {
                return false;
            }
            lastVisited = current.val;
            current = current.right;
        } else {
            TreeNode predecessor = current.left;
            while (predecessor.right != null && predecessor.right != current) {
                predecessor = predecessor.right;
            }
            
            if (predecessor.right == null) {
                predecessor.right = current;
                current = current.left;
            } else {
                predecessor.right = null;
                if (lastVisited != null && current.val <= lastVisited) {
                    return false;
                }
                lastVisited = current.val;
                current = current.right;
            }
        }
    }
    return true;
}

Optimization Criteria

Morris traversal excels when memory constraints prohibit O(h) stack allocation or when processing massive trees where recursion risks stack overflow. However, for algorithms requiring post-order aggregation where parent node calculations depend on comprehensive data from both subtrees, traditional recursive approaches with explicit state passing often provide more intuitive implemantations despite their linear space requirements.