Tree Traversals

Iterative DFS Traversals

Why Iterative?

Recursive traversals use O(h) stack space. Iterative approaches give explicit control and avoid stack overflow for deep trees.

Node Definition

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

Iterative Pre-order (Root → Left → Right)

Use a stack, push right first (so left is processed first):

public List<Integer> preorder(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.add(node.val);
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
    return result;
}

Iterative In-order (Left → Root → Right)

Traverse to leftmost, process, then move right:

public List<Integer> inorder(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    De<TreeNode> stack = new ArrayDeque<>();
    TreeNode curr = root;

    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.pop();
        result.add(curr.val);
        curr = curr.right;
    }
    return result;
}

Iterative Post-order (Left → Right → Root)

Two-stack approach or single stack with tracking:

// Two-stack method
public List<Integer> postorder(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    Deque<TreeNode> stack1 = new ArrayDeque<>();
    Deque<TreeNode> stack2 = new ArrayDeque<>();
    stack1.push(root);

    while (!stack1.isEmpty()) {
        TreeNode node = stack1.pop();
        stack2.push(node);
        if (node.left != null) stack1.push(node.left);
        if (node.right != null) stack1.push(node.right);
    }
    while (!stack2.isEmpty()) {
        result.add(stack2.pop().val);
    }
    return result;
}

Morris Traversal - O(1) Space

Uses threaded binary tree concept. No stack or recursion:

public List<Integer> morrisInorder(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    TreeNode curr = root;

    while (curr != null) {
        if (curr.left == null) {
            result.add(curr.val);
            curr = curr.right;
        } else {
            TreeNode predecessor = curr.left;
            while (predecessor.right != null && predecessor.right != curr) {
                predecessor = predecessor.right;
            }
            if (predecessor.right == null) {
                predecessor.right = curr;  // Create thread
                curr = curr.left;
            } else {
                predecessor.right = null;  // Remove thread
                result.add(curr.val);
                curr = curr.right;
            }
        }
    }
    return result;
}

Complexity Comparison

Method	Time	Space
Recursive	O(n)	O(h)
Iterative	O(n)	O(h)
Morris	O(n)	O(1)

BFS Level-Order Traversals

Basic Level-Order

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        result.add(level);
    }
    return result;
}

Zigzag Level-Order

Alternate left-to-right and right-to-left:

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    boolean leftToRight = true;

    while (!queue.isEmpty()) {
        int size = queue.size();
        LinkedList<Integer> level = new LinkedList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            if (leftToRight) {
                level.addLast(node.val);
            } else {
                level.addFirst(node.val);
            }
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        result.add(level);
        leftToRight = !leftToRight;
    }
    return result;
}

Right Side View

public List<Integer> rightSideView(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            if (i == size - 1) result.add(node.val);  // Last in level
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }
    return result;
}

Maximum Width

public int widthOfBinaryTree(TreeNode root) {
    if (root == null) return 0;
    int maxWidth = 0;
    Queue<pair<TreeNode, Integer>> queue = new LinkedList<>();
    queue.offer(new pair<>(root, 0));

    while (!queue.isEmpty()) {
        int size = queue.size();
        int minIndex = queue.peek().getValue();
        int first = 0, last = 0;
        for (int i = 0; i < size; i++) {
            var pair = queue.poll();
            TreeNode node = pair.getKey();
            int index = pair.getValue() - minIndex;  // Normalize
            if (i == 0) first = index;
            if (i == size - 1) last = index;
            if (node.left != null) queue.offer(new pair<>(node.left, 2 * index + 1));
            if (node.right != null) queue.offer(new pair<>(node.right, 2 * index + 2));
        }
        maxWidth = Math.max(maxWidth, last - first + 1);
    }
    return maxWidth;
}

BFS Template

Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
    int size = queue.size();  // Fix size for current level
    for (int i = 0; i < size; i++) {
        TreeNode node = queue.poll();
        // Process node
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
}

Practice Problems

0 / 3 solved

Medium Binary Tree Right Side View

BFS Level-Order

Given the root of a binary tree, imagine yourself standing on the right side of it. Return the values of the nodes you can see.

Example:

Input: root = [1,2,3,null,5,null,4]

Output: [1,3,4]

Rightmost node at each level.

Optimal Solution — O(n) time, O(n) space

BFS, last node per level

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (i == size - 1) result.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
        return result;
    }
}

Edge Cases:

Empty tree
Single node
Left skewed tree

Medium Binary Tree Zigzag Level Order Traversal

BFS with Direction Flag

Return the zigzag level order traversal (left to right, then right to left, etc.).

Example:

Input: root = [3,9,20,null,null,15,7]

Output: [[3],[20,9],[15,7]]

Level 0 L-R, Level 1 R-L, Level 2 L-R.

Optimal Solution — O(n) time, O(n) space

BFS with alternating direction

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean leftToRight = true;
        while (!queue.isEmpty()) {
            int size = queue.size();
            LinkedList<Integer> level = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (leftToRight) level.addLast(node.val);
                else level.addFirst(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            result.add(level);
            leftToRight = !leftToRight;
        }
        return result;
    }
}

Edge Cases:

Single node
Empty tree
Perfect binary tree

Medium Boundary of Binary Tree

Traversal Decomposition

The boundary of a binary tree is the concatenation of the root, the left boundary, the leaves from left-to-right, and the reverse of the right boundary.

Example:

Input: root = [1,null,2,3,4]

Output: [1,3,4,2]

Root -> left boundary -> leaves -> right boundary.

Optimal Solution — O(n) time, O(h) space

Three passes: left boundary, leaves, right boundary

class Solution {
    public List<Integer> boundaryOfBinaryTree(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        result.add(root.val);
        addLeftBoundary(root.left, result);
        addLeaves(root.left, result);
        addLeaves(root.right, result);
        addRightBoundary(root.right, result);
        return result;
    }
    private void addLeftBoundary(TreeNode node, List<Integer> result) {
        while (node != null) {
            if (node.left != null || node.right != null) result.add(node.val);
            node = node.left != null ? node.left : node.right;
        }
    }
    private void addLeaves(TreeNode node, List<Integer> result) {
        if (node == null) return;
        if (node.left == null && node.right == null) { result.add(node.val); return; }
        addLeaves(node.left, result);
        addLeaves(node.right, result);
    }
    private void addRightBoundary(TreeNode node, List<Integer> result) {
        List<Integer> temp = new ArrayList<>();
        while (node != null) {
            if (node.left != null || node.right != null) temp.add(node.val);
            node = node.right != null ? node.right : node.left;
        }
        for (int i = temp.size() - 1; i >= 0; i--) result.add(temp.get(i));
    }
}

Edge Cases:

Single node
Only left children
Only right children

Flashcards

Question

What traversal order does Morris traversal achieve?

Click to reveal answer

Answer

In-order traversal (Left → Root → Right) in O(1) space by threading the tree. It temporarily modifies the tree structure then restores it.

Question

How do you implement BFS level-order traversal?

Click to reveal answer

Answer

Use a Queue. Process level by tracking queue size at start of each level. Add children to queue during processing. O(n) time, O(w) space where w is max width.

Question

Tree Traversals best practices

Click to reveal answer

Answer

Follow SOLID principles, write clean code, test thoroughly, document decisions, and monitor in production.

Revision Notes

Key Takeaways

1. Pre-order: process root first, use for copying/serializing trees
2. In-order: process root between children, gives sorted order in BST
3. Post-order: process root last, use for deleting/computing height
4. BFS: process level-by-level, use for shortest path/level problems

Interview Tips

• Know all three DFS orders both recursively and iteratively
• BFS is preferred for level-based problems and shortest path
• Morris traversal is impressive but know when to mention it
• For iterative post-order, remember the two-stack trick or use one stack with reverse pre-order

Cheat Sheet

Tree Traversals Cheat Sheet

DFS Orders:

Pre-order: Root → Left → Right (stack: push right then left)
In-order: Left → Root → Right (traverse leftmost, process, go right)
Post-order: Left → Right → Root (two-stack or reverse pre-order)

Iterative In-order Template:

Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
    while (curr != null) {
        stack.push(curr);
        curr = curr.left;
    }
    curr = stack.pop();
    process(curr.val);
    curr = curr.right;
}

BFS Level-Order Template:

Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
    int size = queue.size();
    for (int i = 0; i < size; i++) {
        TreeNode node = queue.poll();
        // process node
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
}

Morris In-order (O(1) space):

If no left child: visit, go right
If left child: find predecessor
If predecessor.right is null: thread it, go left
If predecessor.right is current: unthread, visit, go right

Complexity:

Method	Time	Space
Recursive	O(n)	O(h)
Iterative	O(n)	O(h)
Morris	O(n)	O(1)

Iterative DFS Traversals

Why Iterative?

Node Definition

Iterative Pre-order (Root → Left → Right)

Iterative In-order (Left → Root → Right)

Iterative Post-order (Left → Right → Root)

Morris Traversal - O(1) Space

Complexity Comparison

BFS Level-Order Traversals

Basic Level-Order

Zigzag Level-Order

Right Side View

Maximum Width

BFS Template

Practice Problems

Quiz

Flashcards

Revision Notes

Key Takeaways

Interview Tips

Cheat Sheet

Tree Traversals Cheat Sheet