Skip to content
intermediatePhase 4 · Trees & Heaps

Tree Traversals

Master inorder, preorder, postorder, and level-order traversals.

1h
5 problems
Topic Progress0%

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/3solved
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
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
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

Quiz

1. Which traversal uses a stack data structure for iterative implementation?

Question 1 options

2. What is the space complexity of Morris traversal?

Question 2 options

3. What is the primary purpose of Tree Traversals?

Question 3 options

4. What is a common mistake when implementing Tree Traversals?

Question 4 options

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

What is Tree Traversals?

Click to reveal answer

Answer

Tree Traversals is a key concept in software engineering.

Question

When to use Tree Traversals?

Click to reveal answer

Answer

Use Tree Traversals when building production systems that require reliability, scalability, and maintainability.

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):

  1. If no left child: visit, go right
  2. If left child: find predecessor
  3. If predecessor.right is null: thread it, go left
  4. 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)