Data Structures & AlgorithmsLevel-Order Traversal (BFS on Trees)

Level-Order Traversal — BFS on Trees

LevelIntermediate

Duration55 mins

TopicLevel-Order Traversal (BFS on Trees)

4 / 4

Applications: Shortest Path in Unweighted Trees

The Power of BFS: Distance and Shortest Paths

Throughout this module, we've emphasized that level-order traversal visits nodes in order of their distance from the root. This property might seem like a nice observation, but it's actually the foundation of one of the most important applications of BFS: finding shortest paths.

In unweighted structures (where each edge has the same "cost"), BFS doesn't just traverse—it solves shortest path problems optimally. The first time BFS reaches any node, it has found the shortest path to that node. This guarantee makes BFS the algorithm of choice for a wide variety of practical problems.

What You Will Learn

By the end of this page, you will understand why BFS guarantees shortest paths in unweighted structures, be able to compute distances from the root to all nodes, solve minimum depth and closest node problems, see how this extends to graphs, and recognize shortest path problems in disguise.

Why BFS Finds Shortest Paths

Let's establish rigorously why BFS discovers shortest paths in unweighted structures. This understanding is fundamental and extends far beyond trees.

Key Insight: Level = Distance

In a tree rooted at some node r, the level of any node v equals the number of edges on the path from r to v. Since the tree is connected and acyclic, there's exactly one path between any two nodes, and the level directly measures path length.

BFS Level-Order Property:

BFS visits nodes in non-decreasing order of their level. All nodes at level k are visited before any node at level k+1.

Theorem: In BFS traversal of an unweighted tree (or graph),
         when a node v is first visited, the path taken to reach v
         is a shortest path from the source.
 
Proof (for trees):
1. In a tree, there is exactly ONE path between any two nodes.
2. BFS visits nodes in level order (distance order from root).
3. When BFS visits node v at level k:
   - v is at distance k from the root (by definition of level)
   - BFS has processed all nodes at levels 0, 1, ..., k-1
   - Therefore, v is reached via the unique path of length k
4. Since there's only one path, it is trivially the shortest.
 
For graphs (preview):
1. Multiple paths may exist between nodes.
2. BFS explores paths in order of length.
3. First discovery of v uses a path of length k.
4. Any other path to v would be discovered later (≥ k length).
5. Therefore, first discovery is via shortest path.
 
Conclusion: BFS inherently computes shortest distances.

The Wavefront Intuition:

Imagine dropping a stone in a pond at the root. Ripples expand outward uniformly—all points at distance 1 are reached before any point at distance 2. BFS behaves exactly like this wavefront. It expands uniformly in all directions, reaching closer nodes before farther ones.

This is fundamentally different from DFS, which dives deep along one path before exploring others. DFS might reach a distant node before a nearby one, making it unsuitable for shortest-path computations.

Critical Condition: Unweighted Edges

This property holds only when all edges have equal weight (typically 1). If edges have different weights, BFS no longer guarantees shortest paths—you'd need Dijkstra's algorithm or similar. For trees with unit-weight edges, BFS is optimal.

Weighted vs Unweighted

BFS finds shortest paths only in unweighted or uniformly weighted structures. If edge weights vary (e.g., some edges cost 1, others cost 5), use Dijkstra's algorithm instead. This is a common interview trap—recognize when BFS applies and when it doesn't.

Computing Distances from the Root

A direct application of BFS is computing the distance (in edges) from the root to every node in the tree. This is equivalent to computing the level of each node.

Approaches:

Level-based: Use level-by-level BFS; all nodes in iteration k are at distance k.
Parent-based: When enqueueing a child, set its distance to parent's distance + 1.

Both are O(n) time and O(n) space for storing distances.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * Compute the distance from root to every node.
 * Returns a Map from node to its distance from root.
 * 
 * Time Complexity: O(n)
 * Space Complexity: O(n)
 */
function computeDistances(root: TreeNode | null): Map<TreeNode, number> {
    const distances = new Map<TreeNode, number>();
    
    if (!root) return distances;
    
    const queue: TreeNode[] = [root];
    let currentLevel = 0;
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift()!;
            distances.set(node, currentLevel);
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
        currentLevel++; // Next iteration processes the next level
    }
    
    return distances;
}
 
// Example usage:
// Tree:     1 (distance 0)
//          / \
//  (d=1)  2   3 (d=1)
//        / \
// (d=2) 4   5 (d=2)
//
// distances.get(node4) === 2
// distances.get(root) === 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Alternative: Track distance incrementally as children are discovered.
 * Each node's distance = parent's distance + 1.
 */
function computeDistancesIncremental(root: TreeNode | null): Map<TreeNode, number> {
    const distances = new Map<TreeNode, number>();
    
    if (!root) return distances;
    
    // Queue stores [node, distance] pairs
    const queue: [TreeNode, number][] = [[root, 0]];
    
    while (queue.length > 0) {
        const [node, dist] = queue.shift()!;
        distances.set(node, dist);
        
        // Children are 1 edge farther from root
        if (node.left) queue.push([node.left, dist + 1]);
        if (node.right) queue.push([node.right, dist + 1]);
    }
    
    return distances;
}
 
// This approach is useful when:
// - You don't need to process entire levels together
// - Each node's processing depends on knowing its exact distance
// - You're extending to graphs where level-size approach is less natural

Applications of Distance Computation:

Depth queries: After precomputing distances, answer "what is the depth of node X?" in O(1).
Filtering by distance: Find all nodes within distance k of the root.
Aggregate statistics: Average depth of leaves, distribution of nodes by depth.
Reconstruction problems: Some algorithms need distances during tree reconstruction.
Path length verification: Verify that a claimed path length is correct.

Choosing the Approach

Use level-based BFS when you need to process or compare nodes within the same level. Use incremental distance tracking when each node's processing is independent and you just need individual distances. Both give the same final distances.

Minimum Depth of Binary Tree

One of the most elegant demonstrations of BFS's shortest-path property is the minimum depth problem: find the shortest distance from the root to any leaf node.

Why BFS Excels Here:

BFS explores by distance. The first leaf encountered is, by definition, the closest leaf. We can stop immediately—no need to continue the traversal or compare multiple paths. DFS, by contrast, must explore all paths to find which is shortest.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * Find the minimum depth of a binary tree.
 * Minimum depth = number of edges from root to the closest leaf.
 * 
 * A leaf is a node with no children.
 * 
 * Time Complexity: O(n) worst case, often much better (early termination)
 * Space Complexity: O(w) where w is maximum width
 */
function minDepth(root: TreeNode | null): number {
    if (!root) return 0;
    
    const queue: TreeNode[] = [root];
    let depth = 1; // Root is at depth 1 (or 0, depending on convention)
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift()!;
            
            // Check if this is a leaf
            if (!node.left && !node.right) {
                return depth; // FOUND! First leaf = closest leaf
            }
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
        depth++; // Move to next level
    }
    
    return depth; // Should never reach here if tree is non-empty
}
 
// Example:
// Tree:     1
//          / \
//         2   3     <- 3 is a leaf at depth 2
//        / \
//       4   5
//
// BFS visits: 1, then 2, 3
// At node 3: no children -> leaf found at depth 2
// Return 2 (no need to visit 4 or 5!)

Consider this tree:
 
                1
               / \
              2   3
             / \
            4   5
           / \
          6   7
         / \
        8   9
       /
      10
 
Minimum depth = 2 (path: 1 → 3)
 
BFS Performance:
- Visits: 1, 2, 3
- At node 3: leaf found!
- Nodes visited: 3
- Early termination: YES
 
DFS Performance:
- Must explore left subtree completely (1-2-4-6-8-10)
- Then explore 8→9, 6→7, 4→5, 2→... finally reaches 3
- Nodes visited: 10 (all of them)
- Early termination: NO (must compare all paths)
 
For trees with very different subtree depths, BFS can be 
dramatically more efficient than DFS for minimum depth.

Common Variation: Maximum Depth

Interestingly, for maximum depth, DFS is often simpler:

function maxDepth(root: TreeNode | null): number {
    if (!root) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

BFS can also find maximum depth (just count levels until queue empties), but there's no early termination advantage—you must visit all nodes regardless.

Key Insight:

BFS is superior when you want the first occurrence of something (minimum depth, closest target). DFS is natural when you need to aggregate over all paths (maximum depth, total path sums).

Edge Case: Root Only

When the tree has only a root (no children), the root itself is a leaf. Minimum depth is 1 (or 0, depending on whether you count nodes or edges). Be clear about the problem's definition, as different sources use different conventions.

Finding the Closest Node Satisfying a Condition

A generalization of minimum depth: given a condition, find the closest node to the root that satisfies it. BFS explores by distance, so the first matching node found is the closest.

Pattern:

BFS from the root
For each node, check the condition
Return immediately on first match
If no match, continue until queue empties

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * Find the closest node to the root with the given value.
 * Returns the node if found, null otherwise.
 * 
 * "Closest" means minimum number of edges from root.
 */
function findClosestWithValue(root: TreeNode | null, target: number): TreeNode | null {
    if (!root) return null;
    
    const queue: TreeNode[] = [root];
    
    while (queue.length > 0) {
        const node = queue.shift()!;
        
        // Check condition - first match is closest
        if (node.val === target) {
            return node;
        }
        
        if (node.left) queue.push(node.left);
        if (node.right) queue.push(node.right);
    }
    
    return null; // Target not found
}
 
// Note: If we needed the DISTANCE too:
function findClosestWithValueAndDistance(
    root: TreeNode | null, 
    target: number
): [TreeNode | null, number] {
    if (!root) return [null, -1];
    
    const queue: [TreeNode, number][] = [[root, 0]];
    
    while (queue.length > 0) {
        const [node, dist] = queue.shift()!;
        
        if (node.val === target) {
            return [node, dist];
        }
        
        if (node.left) queue.push([node.left, dist + 1]);
        if (node.right) queue.push([node.right, dist + 1]);
    }
    
    return [null, -1];
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Generic version: find closest node satisfying any predicate.
 * 
 * @param root - Tree root
 * @param predicate - Function that returns true for target nodes
 * @returns The closest node satisfying predicate, or null
 */
function findClosest(
    root: TreeNode | null, 
    predicate: (node: TreeNode) => boolean
): TreeNode | null {
    if (!root) return null;
    
    const queue: TreeNode[] = [root];
    
    while (queue.length > 0) {
        const node = queue.shift()!;
        
        if (predicate(node)) {
            return node; // First match = closest
        }
        
        if (node.left) queue.push(node.left);
        if (node.right) queue.push(node.right);
    }
    
    return null;
}
 
// Example usages:
// Find closest leaf:        findClosest(root, n => !n.left && !n.right)
// Find closest even value:  findClosest(root, n => n.val % 2 === 0)
// Find closest in range:    findClosest(root, n => n.val >= 10 && n.val <= 20)
// Find closest with child:  findClosest(root, n => n.left !== null || n.right !== null)

Real-World Applications:

File System Search: Find the file matching a pattern closest to the root directory.
Organization Hierarchy: Find the closest manager with budget approval authority.
DOM Traversal: Find the closest ancestor element with a specific class.
Game AI: Find the closest enemy unit satisfying certain conditions.
Network Routing: Find the closest server with available capacity.

The pattern is universal: when "closest" in terms of hops/edges matters, BFS is your tool.

Early Termination Efficiency

Unlike DFS which must explore deeply before backtracking, BFS checks nodes in distance order. On average, BFS finds closer nodes faster because it doesn't waste time exploring distant branches before nearby ones. This can be a significant practical performance advantage.

Shortest Path Between Two Nodes in a Tree

In a tree, there's exactly one path between any two nodes (since trees are acyclic and connected). To find this path's length using BFS, we can:

Find the Lowest Common Ancestor (LCA) of the two nodes
Distance = dist(node1, LCA) + dist(node2, LCA)

Alternatively, we can conceptually treat the tree as an undirected graph and BFS from one node to the other.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/**
 * Find the distance (number of edges) between two nodes.
 * Uses LCA to compute: dist(a, b) = depth(a) + depth(b) - 2*depth(LCA(a,b))
 */
function distanceBetweenNodes(
    root: TreeNode | null, 
    p: TreeNode, 
    q: TreeNode
): number {
    // Step 1: Compute depths of all nodes using BFS
    const depths = new Map<TreeNode, number>();
    const parents = new Map<TreeNode, TreeNode | null>();
    
    if (!root) return -1;
    
    const queue: TreeNode[] = [root];
    depths.set(root, 0);
    parents.set(root, null);
    
    while (queue.length > 0) {
        const node = queue.shift()!;
        const depth = depths.get(node)!;
        
        if (node.left) {
            depths.set(node.left, depth + 1);
            parents.set(node.left, node);
            queue.push(node.left);
        }
        if (node.right) {
            depths.set(node.right, depth + 1);
            parents.set(node.right, node);
            queue.push(node.right);
        }
    }
    
    // Step 2: Find LCA by walking up from both nodes
    const ancestorsOfP = new Set<TreeNode>();
    let current: TreeNode | null = p;
    while (current) {
        ancestorsOfP.add(current);
        current = parents.get(current) || null;
    }
    
    let lca: TreeNode | null = q;
    while (lca && !ancestorsOfP.has(lca)) {
        lca = parents.get(lca) || null;
    }
    
    if (!lca) return -1; // Nodes not in same tree
    
    // Step 3: Compute distance
    const depthP = depths.get(p)!;
    const depthQ = depths.get(q)!;
    const depthLCA = depths.get(lca)!;
    
    return (depthP - depthLCA) + (depthQ - depthLCA);
}
 
// Distance formula: dist(p, q) = depth(p) + depth(q) - 2 * depth(LCA)
// This works because the path from p to q goes up to LCA then down.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
 * Treat tree as undirected graph. BFS from source to find distance to target.
 * Requires parent pointers (built first).
 */
function distanceBFSStyle(
    root: TreeNode | null, 
    source: TreeNode, 
    target: TreeNode
): number {
    if (!root || source === target) return source === target ? 0 : -1;
    
    // Build parent map via BFS
    const parents = new Map<TreeNode, TreeNode | null>();
    const queue1: TreeNode[] = [root];
    parents.set(root, null);
    
    while (queue1.length > 0) {
        const node = queue1.shift()!;
        if (node.left) {
            parents.set(node.left, node);
            queue1.push(node.left);
        }
        if (node.right) {
            parents.set(node.right, node);
            queue1.push(node.right);
        }
    }
    
    // BFS from source, considering parent as a neighbor
    const visited = new Set<TreeNode>();
    const queue2: [TreeNode, number][] = [[source, 0]];
    visited.add(source);
    
    while (queue2.length > 0) {
        const [node, dist] = queue2.shift()!;
        
        if (node === target) return dist;
        
        // "Neighbors" in tree-as-graph: parent, left child, right child
        const neighbors = [
            parents.get(node),
            node.left,
            node.right
        ].filter((n): n is TreeNode => n !== null && n !== undefined);
        
        for (const neighbor of neighbors) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue2.push([neighbor, dist + 1]);
            }
        }
    }
    
    return -1; // Target not reachable (shouldn't happen in valid tree)
}

Two Approaches Compared:

Aspect	LCA Approach	BFS Graph-Style
Preprocessing	Build depth + parent maps	Build parent map only
Per-query cost	O(h) to find LCA	O(n) BFS from source
Multiple queries	Better (precompute once)	Worse (BFS per query)
Conceptual	Math-based (depth formula)	Explores path directly

When to Use Which:

Single query: Either works; graph-style is more intuitive.
Many queries: LCA approach with preprocessing is more efficient.
Need the actual path: Graph-style BFS can be adapted to reconstruct the path.
General understanding: Graph-style helps bridge to general graph algorithms.

Trees as Simple Graphs

Treating trees as undirected graphs (adding parent edges) is a powerful mental model. It unifies tree and graph algorithms, and the BFS shortest-path logic works identically in both. This perspective will be valuable when you study graph algorithms.

All Nodes at Distance K from a Target

A beautiful application that combines several concepts: given a target node and distance K, find all nodes exactly K edges away from the target. This is a classic interview problem that elegantly demonstrates BFS.

The challenge is that "distance K" can include nodes in the parent's direction, not just descendants. We need to treat the tree as an undirected graph.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
/**
 * Find all nodes at distance K from the target node.
 * 
 * LeetCode 863: All Nodes Distance K in Binary Tree
 * 
 * Approach:
 * 1. Build parent pointers (so we can go "up" the tree)
 * 2. BFS from target node, treating tree as undirected graph
 * 3. Stop at distance K and collect all nodes
 */
function distanceK(
    root: TreeNode | null, 
    target: TreeNode, 
    k: number
): number[] {
    if (!root) return [];
    
    // Step 1: Build parent map via BFS
    const parents = new Map<TreeNode, TreeNode | null>();
    const queue1: TreeNode[] = [root];
    parents.set(root, null);
    
    while (queue1.length > 0) {
        const node = queue1.shift()!;
        if (node.left) {
            parents.set(node.left, node);
            queue1.push(node.left);
        }
        if (node.right) {
            parents.set(node.right, node);
            queue1.push(node.right);
        }
    }
    
    // Step 2: BFS from target, collecting nodes at distance K
    const visited = new Set<TreeNode>();
    const queue2: [TreeNode, number][] = [[target, 0]];
    visited.add(target);
    const result: number[] = [];
    
    while (queue2.length > 0) {
        const [node, dist] = queue2.shift()!;
        
        if (dist === k) {
            // Collect all nodes at this distance
            result.push(node.val);
            continue; // Don't explore further from this node
        }
        
        // Explore "neighbors": parent, left, right
        const neighbors: (TreeNode | null | undefined)[] = [
            parents.get(node),
            node.left,
            node.right
        ];
        
        for (const neighbor of neighbors) {
            if (neighbor && !visited.has(neighbor)) {
                visited.add(neighbor);
                queue2.push([neighbor, dist + 1]);
            }
        }
    }
    
    return result;
}
 
// Example:
//        3
//       / \
//      5   1
//     / \ / \
//    6  2 0  8
//      / \
//     7   4
//
// target = 5, k = 2
// Nodes at distance 2 from 5: [7, 4, 1]
// - 7 is 5's grandchild (down 2)
// - 4 is 5's grandchild (down 2)
// - 1 is 5's sibling (up 1 to 3, down 1 to 1)

Why This Problem is Beautiful:

Requires bidirectional thinking: We must consider both descendants and ancestors.
Parent map construction: Demonstrates an important preprocessing technique.
Tree-as-graph perspective: Shows how BFS extends naturally when we add parent edges.
Level-based collection: Uses BFS's layer-by-layer property to find all nodes at exact distance.

Optimization Note:

For distance K, we only need to explore K + 1 levels from the target. We can stop BFS early once we've collected all distance-K nodes. The solution above does this by not enqueueing nodes beyond distance K.

The Parent Map Pattern

Building a parent map via BFS is a reusable pattern. Any problem requiring "upward" traversal in a tree (ancestors, path to root, LCA, distance to other nodes) benefits from this preprocessing step. Store it in your mental toolkit.

Extension to Graphs: A Preview

Everything we've learned about BFS on trees extends directly to graphs. The core algorithm is nearly identical—with one crucial addition: cycle detection.

The Key Difference:

In a tree, we can only reach a node from its parent. Once visited, a node won't be encountered again.

In a graph, cycles exist. A node might be reachable from multiple paths. We must track visited nodes to avoid:

Infinite loops
Processing the same node multiple times
Counting incorrect distances (re-discovering a node doesn't mean a shorter path)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * BFS on an unweighted graph (adjacency list representation).
 * Finds shortest distances from source to all reachable nodes.
 */
function bfsGraph(
    graph: Map<number, number[]>, 
    source: number
): Map<number, number> {
    const distances = new Map<number, number>();
    const visited = new Set<number>();  // CRITICAL for graphs!
    const queue: [number, number][] = [[source, 0]];
    
    visited.add(source);
    
    while (queue.length > 0) {
        const [node, dist] = queue.shift()!;
        distances.set(node, dist);
        
        // Explore all neighbors
        for (const neighbor of graph.get(node) || []) {
            if (!visited.has(neighbor)) {  // Only visit once!
                visited.add(neighbor);
                queue.push([neighbor, dist + 1]);
            }
        }
    }
    
    return distances;
}
 
// Key differences from tree BFS:
// 1. "Neighbors" come from adjacency list, not left/right children
// 2. "Visited" set prevents re-visiting nodes (handles cycles)
// 3. We add to visited WHEN ENQUEUEING, not when dequeuing
//    (This is important for graphs to prevent duplicate enqueues)

Why Trees Don't Need Visited Tracking:

In trees:

Each node has exactly one parent
We only enqueue children (going down)
A child can't be reached via another path
No cycles exist

So we never encounter the same node twice naturally.

When Trees Become Graph-Like:

When we add parent pointers (as in "nodes at distance K"), the tree becomes an undirected graph. Now we do need visited tracking, because:

From a child, we might try to go to parent
From parent, we might try to go back to child

This is exactly what we did in the previous section. The parent-pointer extension bridges tree and graph thinking.

BFS: Trees vs Graphs
Aspect	Trees	Graphs
Structure	Hierarchical, one parent per node	Can have cycles, multiple paths
Neighbors	Children (and optionally parent)	All adjacent nodes
Visited tracking	Usually unnecessary	Essential to prevent infinite loops
Shortest path guarantee	Yes (edges = level)	Yes (first discovery = shortest)
Mark visited when?	N/A	When enqueueing (not dequeuing!)

Coming Attraction

Graph BFS is covered in depth in later chapters on graph algorithms. The foundation you've built here—understanding why BFS finds shortest paths and how to implement it—will transfer directly. Trees are just a special case of graphs.

Summary: BFS and Shortest Paths

Let's consolidate the key insights about BFS and its shortest-path applications.

Key Takeaways

•BFS visits nodes in distance order. Level = distance from source. This is the foundational property that enables shortest-path finding.
•First discovery = shortest path. In unweighted structures, when BFS first reaches a node, it has found the minimum-edge path to that node.
•Works only for unweighted/uniform-weight edges. If edge weights vary, use Dijkstra's algorithm instead.
•Minimum depth uses early termination. BFS finds the closest leaf faster than DFS because it checks nodes by distance, not by subtree.
•"Closest satisfying condition" problems are BFS problems. First match = closest match. Generalize to any predicate.
•Parent maps enable upward traversal. By adding parent pointers, we can treat trees as undirected graphs and apply full BFS.
•"Nodes at distance K" combines all concepts: Parent map + graph-style BFS + level-based collection.
•Tree BFS extends to graph BFS with the addition of visited tracking to handle cycles.

Module Complete:

Congratulations! You've completed the module on Level-Order Traversal (BFS on Trees). You now possess:

Conceptual understanding of what level-order traversal is and how it differs from depth-first approaches
Implementation skills for both basic BFS and level-by-level variants
Problem-solving patterns for level-based problems like right side view, level averages, and zigzag traversal
Shortest path intuition that extends naturally to graph algorithms

These skills form a crucial part of your algorithmic toolkit. BFS is one of the most versatile algorithms in computer science—from tree traversal to graph exploration to AI game-playing to network routing. What you've learned here is truly foundational.

Module Complete

You've mastered level-order traversal and its applications to shortest paths. The BFS algorithm, the queue-based implementation, level-aware processing, and shortest-path guarantees are now part of your permanent algorithmic vocabulary. This knowledge will serve you in interviews, production systems, and deeper algorithmic study.

4 / 4

Loading learning content...

Data Structures & AlgorithmsLevel-Order Traversal (BFS on Trees)

Level-Order Traversal — BFS on Trees

LevelIntermediate

Duration55 mins

TopicLevel-Order Traversal (BFS on Trees)

4 / 4

Applications: Shortest Path in Unweighted Trees

The Power of BFS: Distance and Shortest Paths

What You Will Learn

Why BFS Finds Shortest Paths

Let's establish rigorously why BFS discovers shortest paths in unweighted structures. This understanding is fundamental and extends far beyond trees.

Key Insight: Level = Distance

BFS Level-Order Property:

BFS visits nodes in non-decreasing order of their level. All nodes at level k are visited before any node at level k+1.

Theorem: In BFS traversal of an unweighted tree (or graph),
         when a node v is first visited, the path taken to reach v
         is a shortest path from the source.
 
Proof (for trees):
1. In a tree, there is exactly ONE path between any two nodes.
2. BFS visits nodes in level order (distance order from root).
3. When BFS visits node v at level k:
   - v is at distance k from the root (by definition of level)
   - BFS has processed all nodes at levels 0, 1, ..., k-1
   - Therefore, v is reached via the unique path of length k
4. Since there's only one path, it is trivially the shortest.
 
For graphs (preview):
1. Multiple paths may exist between nodes.
2. BFS explores paths in order of length.
3. First discovery of v uses a path of length k.
4. Any other path to v would be discovered later (≥ k length).
5. Therefore, first discovery is via shortest path.
 
Conclusion: BFS inherently computes shortest distances.

The Wavefront Intuition:

Critical Condition: Unweighted Edges

Weighted vs Unweighted

Computing Distances from the Root

A direct application of BFS is computing the distance (in edges) from the root to every node in the tree. This is equivalent to computing the level of each node.

Approaches:

Level-based: Use level-by-level BFS; all nodes in iteration k are at distance k.
Parent-based: When enqueueing a child, set its distance to parent's distance + 1.

Both are O(n) time and O(n) space for storing distances.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * Compute the distance from root to every node.
 * Returns a Map from node to its distance from root.
 * 
 * Time Complexity: O(n)
 * Space Complexity: O(n)
 */
function computeDistances(root: TreeNode | null): Map<TreeNode, number> {
    const distances = new Map<TreeNode, number>();
    
    if (!root) return distances;
    
    const queue: TreeNode[] = [root];
    let currentLevel = 0;
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift()!;
            distances.set(node, currentLevel);
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
        currentLevel++; // Next iteration processes the next level
    }
    
    return distances;
}
 
// Example usage:
// Tree:     1 (distance 0)
//          / \
//  (d=1)  2   3 (d=1)
//        / \
// (d=2) 4   5 (d=2)
//
// distances.get(node4) === 2
// distances.get(root) === 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Alternative: Track distance incrementally as children are discovered.
 * Each node's distance = parent's distance + 1.
 */
function computeDistancesIncremental(root: TreeNode | null): Map<TreeNode, number> {
    const distances = new Map<TreeNode, number>();
    
    if (!root) return distances;
    
    // Queue stores [node, distance] pairs
    const queue: [TreeNode, number][] = [[root, 0]];
    
    while (queue.length > 0) {
        const [node, dist] = queue.shift()!;
        distances.set(node, dist);
        
        // Children are 1 edge farther from root
        if (node.left) queue.push([node.left, dist + 1]);
        if (node.right) queue.push([node.right, dist + 1]);
    }
    
    return distances;
}
 
// This approach is useful when:
// - You don't need to process entire levels together
// - Each node's processing depends on knowing its exact distance
// - You're extending to graphs where level-size approach is less natural

Applications of Distance Computation:

Depth queries: After precomputing distances, answer "what is the depth of node X?" in O(1).
Filtering by distance: Find all nodes within distance k of the root.
Aggregate statistics: Average depth of leaves, distribution of nodes by depth.
Reconstruction problems: Some algorithms need distances during tree reconstruction.
Path length verification: Verify that a claimed path length is correct.

Choosing the Approach

Minimum Depth of Binary Tree

One of the most elegant demonstrations of BFS's shortest-path property is the minimum depth problem: find the shortest distance from the root to any leaf node.

Why BFS Excels Here:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * Find the minimum depth of a binary tree.
 * Minimum depth = number of edges from root to the closest leaf.
 * 
 * A leaf is a node with no children.
 * 
 * Time Complexity: O(n) worst case, often much better (early termination)
 * Space Complexity: O(w) where w is maximum width
 */
function minDepth(root: TreeNode | null): number {
    if (!root) return 0;
    
    const queue: TreeNode[] = [root];
    let depth = 1; // Root is at depth 1 (or 0, depending on convention)
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift()!;
            
            // Check if this is a leaf
            if (!node.left && !node.right) {
                return depth; // FOUND! First leaf = closest leaf
            }
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
        depth++; // Move to next level
    }
    
    return depth; // Should never reach here if tree is non-empty
}
 
// Example:
// Tree:     1
//          / \
//         2   3     <- 3 is a leaf at depth 2
//        / \
//       4   5
//
// BFS visits: 1, then 2, 3
// At node 3: no children -> leaf found at depth 2
// Return 2 (no need to visit 4 or 5!)

Consider this tree:
 
                1
               / \
              2   3
             / \
            4   5
           / \
          6   7
         / \
        8   9
       /
      10
 
Minimum depth = 2 (path: 1 → 3)
 
BFS Performance:
- Visits: 1, 2, 3
- At node 3: leaf found!
- Nodes visited: 3
- Early termination: YES
 
DFS Performance:
- Must explore left subtree completely (1-2-4-6-8-10)
- Then explore 8→9, 6→7, 4→5, 2→... finally reaches 3
- Nodes visited: 10 (all of them)
- Early termination: NO (must compare all paths)
 
For trees with very different subtree depths, BFS can be 
dramatically more efficient than DFS for minimum depth.

Common Variation: Maximum Depth

Interestingly, for maximum depth, DFS is often simpler:

function maxDepth(root: TreeNode | null): number {
    if (!root) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

BFS can also find maximum depth (just count levels until queue empties), but there's no early termination advantage—you must visit all nodes regardless.

Key Insight:

BFS is superior when you want the first occurrence of something (minimum depth, closest target). DFS is natural when you need to aggregate over all paths (maximum depth, total path sums).

Edge Case: Root Only

Finding the Closest Node Satisfying a Condition

A generalization of minimum depth: given a condition, find the closest node to the root that satisfies it. BFS explores by distance, so the first matching node found is the closest.

Pattern:

BFS from the root
For each node, check the condition
Return immediately on first match
If no match, continue until queue empties

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * Find the closest node to the root with the given value.
 * Returns the node if found, null otherwise.
 * 
 * "Closest" means minimum number of edges from root.
 */
function findClosestWithValue(root: TreeNode | null, target: number): TreeNode | null {
    if (!root) return null;
    
    const queue: TreeNode[] = [root];
    
    while (queue.length > 0) {
        const node = queue.shift()!;
        
        // Check condition - first match is closest
        if (node.val === target) {
            return node;
        }
        
        if (node.left) queue.push(node.left);
        if (node.right) queue.push(node.right);
    }
    
    return null; // Target not found
}
 
// Note: If we needed the DISTANCE too:
function findClosestWithValueAndDistance(
    root: TreeNode | null, 
    target: number
): [TreeNode | null, number] {
    if (!root) return [null, -1];
    
    const queue: [TreeNode, number][] = [[root, 0]];
    
    while (queue.length > 0) {
        const [node, dist] = queue.shift()!;
        
        if (node.val === target) {
            return [node, dist];
        }
        
        if (node.left) queue.push([node.left, dist + 1]);
        if (node.right) queue.push([node.right, dist + 1]);
    }
    
    return [null, -1];
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Generic version: find closest node satisfying any predicate.
 * 
 * @param root - Tree root
 * @param predicate - Function that returns true for target nodes
 * @returns The closest node satisfying predicate, or null
 */
function findClosest(
    root: TreeNode | null, 
    predicate: (node: TreeNode) => boolean
): TreeNode | null {
    if (!root) return null;
    
    const queue: TreeNode[] = [root];
    
    while (queue.length > 0) {
        const node = queue.shift()!;
        
        if (predicate(node)) {
            return node; // First match = closest
        }
        
        if (node.left) queue.push(node.left);
        if (node.right) queue.push(node.right);
    }
    
    return null;
}
 
// Example usages:
// Find closest leaf:        findClosest(root, n => !n.left && !n.right)
// Find closest even value:  findClosest(root, n => n.val % 2 === 0)
// Find closest in range:    findClosest(root, n => n.val >= 10 && n.val <= 20)
// Find closest with child:  findClosest(root, n => n.left !== null || n.right !== null)

Real-World Applications:

File System Search: Find the file matching a pattern closest to the root directory.
Organization Hierarchy: Find the closest manager with budget approval authority.
DOM Traversal: Find the closest ancestor element with a specific class.
Game AI: Find the closest enemy unit satisfying certain conditions.
Network Routing: Find the closest server with available capacity.

The pattern is universal: when "closest" in terms of hops/edges matters, BFS is your tool.

Early Termination Efficiency

Shortest Path Between Two Nodes in a Tree

In a tree, there's exactly one path between any two nodes (since trees are acyclic and connected). To find this path's length using BFS, we can:

Find the Lowest Common Ancestor (LCA) of the two nodes
Distance = dist(node1, LCA) + dist(node2, LCA)

Alternatively, we can conceptually treat the tree as an undirected graph and BFS from one node to the other.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/**
 * Find the distance (number of edges) between two nodes.
 * Uses LCA to compute: dist(a, b) = depth(a) + depth(b) - 2*depth(LCA(a,b))
 */
function distanceBetweenNodes(
    root: TreeNode | null, 
    p: TreeNode, 
    q: TreeNode
): number {
    // Step 1: Compute depths of all nodes using BFS
    const depths = new Map<TreeNode, number>();
    const parents = new Map<TreeNode, TreeNode | null>();
    
    if (!root) return -1;
    
    const queue: TreeNode[] = [root];
    depths.set(root, 0);
    parents.set(root, null);
    
    while (queue.length > 0) {
        const node = queue.shift()!;
        const depth = depths.get(node)!;
        
        if (node.left) {
            depths.set(node.left, depth + 1);
            parents.set(node.left, node);
            queue.push(node.left);
        }
        if (node.right) {
            depths.set(node.right, depth + 1);
            parents.set(node.right, node);
            queue.push(node.right);
        }
    }
    
    // Step 2: Find LCA by walking up from both nodes
    const ancestorsOfP = new Set<TreeNode>();
    let current: TreeNode | null = p;
    while (current) {
        ancestorsOfP.add(current);
        current = parents.get(current) || null;
    }
    
    let lca: TreeNode | null = q;
    while (lca && !ancestorsOfP.has(lca)) {
        lca = parents.get(lca) || null;
    }
    
    if (!lca) return -1; // Nodes not in same tree
    
    // Step 3: Compute distance
    const depthP = depths.get(p)!;
    const depthQ = depths.get(q)!;
    const depthLCA = depths.get(lca)!;
    
    return (depthP - depthLCA) + (depthQ - depthLCA);
}
 
// Distance formula: dist(p, q) = depth(p) + depth(q) - 2 * depth(LCA)
// This works because the path from p to q goes up to LCA then down.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
 * Treat tree as undirected graph. BFS from source to find distance to target.
 * Requires parent pointers (built first).
 */
function distanceBFSStyle(
    root: TreeNode | null, 
    source: TreeNode, 
    target: TreeNode
): number {
    if (!root || source === target) return source === target ? 0 : -1;
    
    // Build parent map via BFS
    const parents = new Map<TreeNode, TreeNode | null>();
    const queue1: TreeNode[] = [root];
    parents.set(root, null);
    
    while (queue1.length > 0) {
        const node = queue1.shift()!;
        if (node.left) {
            parents.set(node.left, node);
            queue1.push(node.left);
        }
        if (node.right) {
            parents.set(node.right, node);
            queue1.push(node.right);
        }
    }
    
    // BFS from source, considering parent as a neighbor
    const visited = new Set<TreeNode>();
    const queue2: [TreeNode, number][] = [[source, 0]];
    visited.add(source);
    
    while (queue2.length > 0) {
        const [node, dist] = queue2.shift()!;
        
        if (node === target) return dist;
        
        // "Neighbors" in tree-as-graph: parent, left child, right child
        const neighbors = [
            parents.get(node),
            node.left,
            node.right
        ].filter((n): n is TreeNode => n !== null && n !== undefined);
        
        for (const neighbor of neighbors) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue2.push([neighbor, dist + 1]);
            }
        }
    }
    
    return -1; // Target not reachable (shouldn't happen in valid tree)
}

Two Approaches Compared:

Aspect	LCA Approach	BFS Graph-Style
Preprocessing	Build depth + parent maps	Build parent map only
Per-query cost	O(h) to find LCA	O(n) BFS from source
Multiple queries	Better (precompute once)	Worse (BFS per query)
Conceptual	Math-based (depth formula)	Explores path directly

When to Use Which:

Single query: Either works; graph-style is more intuitive.
Many queries: LCA approach with preprocessing is more efficient.
Need the actual path: Graph-style BFS can be adapted to reconstruct the path.
General understanding: Graph-style helps bridge to general graph algorithms.

Trees as Simple Graphs

All Nodes at Distance K from a Target

The challenge is that "distance K" can include nodes in the parent's direction, not just descendants. We need to treat the tree as an undirected graph.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
/**
 * Find all nodes at distance K from the target node.
 * 
 * LeetCode 863: All Nodes Distance K in Binary Tree
 * 
 * Approach:
 * 1. Build parent pointers (so we can go "up" the tree)
 * 2. BFS from target node, treating tree as undirected graph
 * 3. Stop at distance K and collect all nodes
 */
function distanceK(
    root: TreeNode | null, 
    target: TreeNode, 
    k: number
): number[] {
    if (!root) return [];
    
    // Step 1: Build parent map via BFS
    const parents = new Map<TreeNode, TreeNode | null>();
    const queue1: TreeNode[] = [root];
    parents.set(root, null);
    
    while (queue1.length > 0) {
        const node = queue1.shift()!;
        if (node.left) {
            parents.set(node.left, node);
            queue1.push(node.left);
        }
        if (node.right) {
            parents.set(node.right, node);
            queue1.push(node.right);
        }
    }
    
    // Step 2: BFS from target, collecting nodes at distance K
    const visited = new Set<TreeNode>();
    const queue2: [TreeNode, number][] = [[target, 0]];
    visited.add(target);
    const result: number[] = [];
    
    while (queue2.length > 0) {
        const [node, dist] = queue2.shift()!;
        
        if (dist === k) {
            // Collect all nodes at this distance
            result.push(node.val);
            continue; // Don't explore further from this node
        }
        
        // Explore "neighbors": parent, left, right
        const neighbors: (TreeNode | null | undefined)[] = [
            parents.get(node),
            node.left,
            node.right
        ];
        
        for (const neighbor of neighbors) {
            if (neighbor && !visited.has(neighbor)) {
                visited.add(neighbor);
                queue2.push([neighbor, dist + 1]);
            }
        }
    }
    
    return result;
}
 
// Example:
//        3
//       / \
//      5   1
//     / \ / \
//    6  2 0  8
//      / \
//     7   4
//
// target = 5, k = 2
// Nodes at distance 2 from 5: [7, 4, 1]
// - 7 is 5's grandchild (down 2)
// - 4 is 5's grandchild (down 2)
// - 1 is 5's sibling (up 1 to 3, down 1 to 1)

Why This Problem is Beautiful:

Requires bidirectional thinking: We must consider both descendants and ancestors.
Parent map construction: Demonstrates an important preprocessing technique.
Tree-as-graph perspective: Shows how BFS extends naturally when we add parent edges.
Level-based collection: Uses BFS's layer-by-layer property to find all nodes at exact distance.

Optimization Note:

The Parent Map Pattern

Extension to Graphs: A Preview

Everything we've learned about BFS on trees extends directly to graphs. The core algorithm is nearly identical—with one crucial addition: cycle detection.

The Key Difference:

In a tree, we can only reach a node from its parent. Once visited, a node won't be encountered again.

In a graph, cycles exist. A node might be reachable from multiple paths. We must track visited nodes to avoid:

Infinite loops
Processing the same node multiple times
Counting incorrect distances (re-discovering a node doesn't mean a shorter path)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * BFS on an unweighted graph (adjacency list representation).
 * Finds shortest distances from source to all reachable nodes.
 */
function bfsGraph(
    graph: Map<number, number[]>, 
    source: number
): Map<number, number> {
    const distances = new Map<number, number>();
    const visited = new Set<number>();  // CRITICAL for graphs!
    const queue: [number, number][] = [[source, 0]];
    
    visited.add(source);
    
    while (queue.length > 0) {
        const [node, dist] = queue.shift()!;
        distances.set(node, dist);
        
        // Explore all neighbors
        for (const neighbor of graph.get(node) || []) {
            if (!visited.has(neighbor)) {  // Only visit once!
                visited.add(neighbor);
                queue.push([neighbor, dist + 1]);
            }
        }
    }
    
    return distances;
}
 
// Key differences from tree BFS:
// 1. "Neighbors" come from adjacency list, not left/right children
// 2. "Visited" set prevents re-visiting nodes (handles cycles)
// 3. We add to visited WHEN ENQUEUEING, not when dequeuing
//    (This is important for graphs to prevent duplicate enqueues)

Why Trees Don't Need Visited Tracking:

In trees:

Each node has exactly one parent
We only enqueue children (going down)
A child can't be reached via another path
No cycles exist

So we never encounter the same node twice naturally.

When Trees Become Graph-Like:

When we add parent pointers (as in "nodes at distance K"), the tree becomes an undirected graph. Now we do need visited tracking, because:

From a child, we might try to go to parent
From parent, we might try to go back to child

This is exactly what we did in the previous section. The parent-pointer extension bridges tree and graph thinking.

BFS: Trees vs Graphs
Aspect	Trees	Graphs
Structure	Hierarchical, one parent per node	Can have cycles, multiple paths
Neighbors	Children (and optionally parent)	All adjacent nodes
Visited tracking	Usually unnecessary	Essential to prevent infinite loops
Shortest path guarantee	Yes (edges = level)	Yes (first discovery = shortest)
Mark visited when?	N/A	When enqueueing (not dequeuing!)

Coming Attraction

Summary: BFS and Shortest Paths

Let's consolidate the key insights about BFS and its shortest-path applications.

Key Takeaways

•BFS visits nodes in distance order. Level = distance from source. This is the foundational property that enables shortest-path finding.
•First discovery = shortest path. In unweighted structures, when BFS first reaches a node, it has found the minimum-edge path to that node.
•Works only for unweighted/uniform-weight edges. If edge weights vary, use Dijkstra's algorithm instead.
•Minimum depth uses early termination. BFS finds the closest leaf faster than DFS because it checks nodes by distance, not by subtree.
•"Closest satisfying condition" problems are BFS problems. First match = closest match. Generalize to any predicate.
•Parent maps enable upward traversal. By adding parent pointers, we can treat trees as undirected graphs and apply full BFS.
•"Nodes at distance K" combines all concepts: Parent map + graph-style BFS + level-based collection.
•Tree BFS extends to graph BFS with the addition of visited tracking to handle cycles.

Module Complete:

Congratulations! You've completed the module on Level-Order Traversal (BFS on Trees). You now possess:

Conceptual understanding of what level-order traversal is and how it differs from depth-first approaches
Implementation skills for both basic BFS and level-by-level variants
Problem-solving patterns for level-based problems like right side view, level averages, and zigzag traversal
Shortest path intuition that extends naturally to graph algorithms

Module Complete

4 / 4