Tree Traversal Interview Questions: BFS vs DFS Guide

BFS explores nodes level by level using a queue, while DFS dives deep into a branch before backtracking using a stack or recursion. Choosing the right traversal is the difference between a clean O(n) solution and a tangled mess in tree interview questions.

When to Use BFS vs DFS

Use BFS when:

• You need the shortest path in an unweighted tree
• You need to process nodes level by level (level-order traversal)
• The problem asks for the minimum depth or fewest steps
• You need to find the closest node satisfying a condition

Use DFS when:

• You need to explore all paths (path sum problems)
• You need to find the deepest node or maximum depth
• You need to find the lowest common ancestor
• The problem involves backtracking or exploring all combinations
• You need to validate structural properties (symmetric tree, balanced tree)

The Trigger Pattern

The interviewer asks "level by level" → BFS. The interviewer asks "any path" or "deepest" → DFS. When in doubt, DFS is the default because it uses O(h) space where h is the height, while BFS always uses O(w) where w is the maximum width.

BFS: Level-Order Traversal

BFS uses a queue to visit all nodes at the current depth before moving to the next level. This is the pattern for any "level by level" problem.

from collections import deque

def level_order_traversal(root):
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)
        current_level = []

        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        result.append(current_level)

    return result

Why this works: The key insight is capturing level_size before processing. This tells you exactly how many nodes belong to the current level. Without this, you cannot separate levels in the output.

Time: O(n) — every node visited once. Space: O(w) — at most one full level in the queue.

DFS: Maximum Depth of Binary Tree

DFS is natural for depth problems because recursion naturally tracks depth through the call stack.

def max_depth(root):
    if not root:
        return 0

    left_depth = max_depth(root.left)
    right_depth = max_depth(root.right)

    return 1 + max(left_depth, right_depth)

Why this works: Each recursive call goes one level deeper. When you hit a leaf, the base case returns 0. As the recursion unwinds, each parent takes the max of its children's depths and adds 1.

Time: O(n) — visit every node. Space: O(h) — recursion stack where h is tree height. Worst case O(n) for skewed tree, O(log n) for balanced.

DFS: Path Sum Problem

Path sum is the classic DFS problem where you check if any root-to-leaf path sums to a target. This demonstrates how DFS explores all paths.

def has_path_sum(root, target_sum):
    if not root:
        return False

    # Leaf node — check if remaining sum matches
    if not root.left and not root.right:
        return root.val == target_sum

    # Recurse with updated remaining sum
    remaining = target_sum - root.val
    return (has_path_sum(root.left, remaining) or
            has_path_sum(root.right, remaining))

Why this works: DFS naturally tracks the current path by passing the remaining sum down. At each node, you subtract its value. At a leaf, if the remaining sum equals the leaf's value, you found a valid path.

Time: O(n) — visit every node in worst case. Space: O(h) — recursion stack.

DFS: Lowest Common Ancestor

The lowest common ancestor (LCA) problem shows the power of post-order DFS, where you process children before the parent.

def lowest_common_ancestor(root, p, q):
    if not root or root == p or root == q:
        return root

    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)

    if left and right:
        return root  # p and q are in different subtrees

    return left if left else right

Why this works: Post-order DFS returns None until it finds p or q. If both left and right return non-None, the current node is the split point — the LCA. If only one side returns non-None, both targets are in that subtree.

Time: O(n) — visit every node. Space: O(h) — recursion stack.

BFS: Binary Tree Right Side View

This problem demonstrates BFS where you need the last node at each level — a common pattern in FAANG interviews.

from collections import deque

def right_side_view(root):
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)

        for i in range(level_size):
            node = queue.popleft()

            # Last node in this level
            if i == level_size - 1:
                result.append(node.val)

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    return result

Why this works: BFS processes nodes left to right within each level. The last node you process at each level is the one visible from the right side.

Time: O(n). Space: O(w) where w is max width.

Common Mistakes

1. Using BFS when DFS is better. BFS uses O(w) space which can be O(n) for a complete tree. DFS uses O(h) which is O(log n) for balanced trees. Use DFS unless you specifically need level-order information.

2. Forgetting to capture level_size in BFS. If you process the queue without knowing how many nodes are in the current level, you cannot separate levels. Always capture len(queue) before the inner loop.

3. Off-by-one errors in path sum. Remember to check the leaf condition before recursing, not after. Checking after means you might miss the case where the root itself is the only node.

4. Confusing pre-order, in-order, and post-order. Pre-order: process node first (good for copying trees). In-order: process node between left and right (gives sorted order for BST). Post-order: process node last (good for deletion, LCA).

5. Not handling empty trees. Always check if not root at the start. An empty tree is a valid tree.

Practice Problems

Start with these problems to master tree traversals:

1. Binary Tree Level Order Traversal — The foundational BFS problem. Returns nodes grouped by level.
2. Maximum Depth of Binary Tree — The simplest DFS problem. Good warmup for recursion on trees.
3. Path Sum — Classic DFS path problem. Teaches how to track state through recursion.
4. Lowest Common Ancestor of a Binary Tree — Tests post-order DFS thinking. Frequently asked at Google and Amazon.
5. Binary Tree Right Side View — Combines BFS with level tracking. Tests whether you can extract information per level.

Practice What You Learned

Ready to put this into practice? Try a mock coding interview with an AI interviewer who can ask you tree traversal questions and evaluate your approach in real time.

Frequently Asked Questions