Binary Tree Traversal (Iteration + Recursion)

Recursive Traversals

Based on the visit order of the root relative to its children:

// Pre-order: Root -> Left -> Right
void preorder(TreeNode root, List<Integer> res) {
    if (root == null) return;
    res.add(root.val);
    preorder(root.left, res);
    preorder(root.right, res);
}

// In-order: Left -> Root -> Right (Ordered output for BST)
void inorder(TreeNode root, List<Integer> res) {
    if (root == null) return;
    inorder(root.left, res);
    res.add(root.val);
    inorder(root.right, res);
}

// Post-order: Left -> Right -> Root
void postorder(TreeNode root, List<Integer> res) {
    if (root == null) return;
    postorder(root.left, res);
    postorder(root.right, res);
    res.add(root.val);
}

Iterative Traversals (Using Explicit Stack)

Pre-order Iteration

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    if (root != null) stack.push(root);
    
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        res.add(node.val);
        // Push Right child first (LIFO means Left child is processed first)
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
    return res;
}

In-order Iteration

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    
    while (cur != null || !stack.isEmpty()) {
        // Step 1: Push all left ancestors to stack
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        // Step 2: Access Root
        cur = stack.pop();
        res.add(cur.val);
        // Step 3: Shift to right subtree
        cur = cur.right;
    }
    return res;
}

Post-order Iteration

A trick: Modified Pre-order (Root-Right-Left) reversed yields (Left-Right-Root).

public List<Integer> postorderTraversal(TreeNode root) {
    LinkedList<Integer> res = new LinkedList<>(); // Use for addFirst()
    Deque<TreeNode> stack = new ArrayDeque<>();
    if (root != null) stack.push(root);
    
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        // Insert at head to achieve reversal effect
        res.addFirst(node.val); 
        if (node.left != null) stack.push(node.left);
        if (node.right != null) stack.push(node.right);
    }
    return res;
}

Level-Order Traversal (BFS)

// LeetCode 102
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        int size = queue.size(); // Current layer node count
        List<Integer> currentLevel = new ArrayList<>();
        
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            currentLevel.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        res.add(currentLevel);
    }
    return res;
}

BFS Variations

• Bottom-Up Level Order (LeetCode 107): Compute standard Level-Order and then call Collections.reverse(res).
• Zigzag Level Order (LeetCode 103):

boolean leftToRight = true;
// ... inside level loop ...
if (leftToRight) currentLevel.add(node.val);
else currentLevel.addFirst(node.val); // Requires LinkedList
// ... after level loop ...
leftToRight = !leftToRight;

Morris Traversal (O(1) Space In-order)

Uses leaf pointers to temporarily point back to ancestors, eliminating the need for a stack or recursion.

public List<Integer> morrisInorder(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    TreeNode cur = root, prev;
    
    while (cur != null) {
        if (cur.left == null) {
            res.add(cur.val);
            cur = cur.right;
        } else {
            // Find in-order predecessor
            prev = cur.left;
            while (prev.right != null && prev.right != cur) {
                prev = prev.right;
            }
            
            if (prev.right == null) {
                prev.right = cur; // Establish threading pointer
                cur = cur.left;
            } else {
                prev.right = null; // Threading pointer found, restore original tree
                res.add(cur.val);
                cur = cur.right;
            }
        }
    }
    return res;
}

Summary Checklist