Trees

BFS (Breadth-First Search)

TimeO(V + E) SpaceO(V)

Think of ripples in a pond. Drop a stone and the ripples expand outward in concentric circles — first the center, then the next ring, then the next. BFS explores a tree the same way: all nodes at depth 1, then depth 2, then depth 3.

When to use it: Level-order traversal, finding the shortest path in an unweighted graph/tree, or any problem that asks about distance or “minimum steps.”

Key insight: A queue naturally processes nodes in the order they were discovered. Processing all nodes at the current depth before any at the next depth gives you level-by-level exploration.

Common trap: Not tracking the level boundary. To process level by level, snapshot the queue size at the start of each level and process exactly that many nodes.

function bfsLevelOrder(root):
    if root == null:
        return []

    result = []
    queue = [root]

    while queue is not empty:
        levelSize = length(queue)       # nodes at current level
        currentLevel = []

        for i = 0 to levelSize - 1:
            node = queue.dequeue()
            currentLevel.append(node.val)

            if node.left != null:
                queue.enqueue(node.left)
            if node.right != null:
                queue.enqueue(node.right)

        result.append(currentLevel)

    return result

from collections import deque


class TreeNode:
    def __init__(self, val: int = 0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def level_order(root: TreeNode | None) -> list[list[int]]:
    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


def min_depth(root: TreeNode | None) -> int:
    """Minimum depth of a binary tree (BFS finds it first)."""
    if not root:
        return 0

    queue = deque([(root, 1)])

    while queue:
        node, depth = queue.popleft()

        if not node.left and not node.right:
            return depth

        if node.left:
            queue.append((node.left, depth + 1))
        if node.right:
            queue.append((node.right, depth + 1))

    return 0

Problem: Given a binary tree, return its values grouped by level (level-order traversal).

How would you approach this?

Answer: This is BFS on a tree. Use a queue and process nodes level by level. At each level, dequeue all current nodes (snapshot the queue size), collect their values, and enqueue their children.

Problem: Given a binary tree, find the minimum number of edges from the root to any leaf.

How would you approach this?

Answer: This is BFS because it explores level by level. The first leaf node BFS encounters is guaranteed to be at the minimum depth. Return its depth immediately — no need to explore the rest of the tree.

Time: O(V + E) where V is the number of nodes and E is the number of edges. In a tree, E = V - 1, so this simplifies to O(V). Each node is enqueued and dequeued exactly once.

Space: O(V) in the worst case because the queue may hold an entire level. For a complete binary tree, the bottom level has ~V/2 nodes. The result array also uses O(V) space.