Binary Tree Level-Order Traversal

In our previous lesson, we explored the "deep" paths of a binary tree using recursive depth-first traversals. We learned to navigate by going as far down one branch as possible before backtracking. Now, we'll shift our perspective from depth to breadth.

This lesson introduces Breadth-First Search (BFS), a traversal strategy that explores a tree level by level. Instead of diving deep, we'll visit all nodes at the current depth before moving on to the next. This "wide" exploration is essential for a different class of problems, such as finding the shortest path in an unweighted graph (a topic we'll cover later) or any task that requires processing nodes in order of their distance from the root.

The key to managing this level-by-level exploration is a data structure you've encountered before: the queue. Its First-In, First-Out (FIFO) property is perfectly suited to ensure we process nodes in the order we discover them. Your experience as a front-end developer has given you an intuition for ordered processing, like handling user events or managing rendering queues, and we'll apply that same principle here in a more structured, algorithmic context.

The Essence of Breadth-First Search

Imagine a tree's nodes are balls connected by strings. If you grab the root node and pull it upwards, the nodes will naturally arrange themselves into layers based on their distance from the root. BFS is the algorithmic equivalent of visiting the nodes in the first layer, then the second, then the third, and so on.

The following video from Reducible provides an excellent analogy to build this intuition. It discusses BFS in the context of general graphs, but the core idea of visiting neighbors level by level applies directly to trees.

As the video explains, the key to implementing this is a queue. Here’s how the process works:

1. Initialize: Create a queue and add the root node to it.
2. Loop: While the queue is not empty:
   a. Dequeue: Remove the node from the front of the queue.
   b. Visit: Process the node (e.g., print its value).
   c. Enqueue Children: Add the node's left child (if it exists) to the back of the queue. Then, add its right child (if it exists) to the back of the queue.

This FIFO process guarantees that nodes added at a certain level are processed completely before the nodes they, in turn, add (which belong to the next level).

This animated GIF provides a perfect visual of the algorithm in action. Watch how nodes are added to the "Frontier Queue" and processed in the order they entered, ensuring a level-by-level traversal.

Grouping Nodes by Level

The basic algorithm described above will visit all nodes in the correct level order, but it will produce a flat list of values (e.g., [A, B, C, D, E, F, G]). In many interview problems, you are required to return the values grouped by level, like [[A], [B, C], [D, E, F, G]].

To achieve this, we need a small but crucial modification to the algorithm. This is a very common interview pattern. The trick is to know, at the start of each level, exactly how many nodes are on that level.

How can we know that? The number of nodes on the current level is simply the current size of the queue.

Here is the refined algorithm:

1. Initialize: Create a queue, add the root node, and create a main result list.
2. Outer Loop: While the queue is not empty:
   a. Get Level Size: Store the current size of the queue in a variable, levelSize.
   b. Initialize Level List: Create a new list for the current level's values, currentLevel.
   c. Inner Loop: Loop levelSize times:
   i. Dequeue: Remove a node from the front of the queue.
   ii. Add to Level: Add the node's value to the currentLevel list.
   iii. Enqueue Children: Add the node's left and right children to the back of the queue.
   d. Add to Result: After the inner loop finishes, add the currentLevel list to the main result list.

This structure ensures that the inner loop processes exactly one level's worth of nodes before the outer loop moves on to the next.

The following video from Andy Gala provides a fantastic, step-by-step walkthrough of this specific technique in JavaScript. It clearly explains the common pitfalls of a naive approach and the elegance of using the queue's length to manage levels.

Implementation in TypeScript

Now, let's translate this logic into a TypeScript function. We'll use our TreeNode class from the previous lessons. For the queue, a standard JavaScript array works well; we'll use push to enqueue and shift to dequeue.

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;

    constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function levelOrder(root: TreeNode | null): number[][] {
    // If the tree is empty, return an empty array.
    if (!root) {
        return [];
    }

    const result: number[][] = [];
    const queue: TreeNode[] = [root];

    // Continue as long as there are nodes to process.
    while (queue.length > 0) {
        // The number of nodes at the current level.
        const levelSize = queue.length;
        const currentLevel: number[] = [];

        // Process exactly `levelSize` nodes.
        for (let i = 0; i < levelSize; i++) {
            // Dequeue the first node in the queue.
            const node = queue.shift()!; // Using '!' since queue.length > 0 check ensures it's not empty.

            // Add its value to the list for the current level.
            currentLevel.push(node.val);

            // Enqueue children for the next level.
            if (node.left) {
                queue.push(node.left);
            }
            if (node.right) {
                queue.push(node.right);
            }
        }
        
        // Add the completed level to the final result.
        result.push(currentLevel);
    }

    return result;
}

Code Walkthrough

Let's trace this function with the tree from the image resource BFS with Queue.

1. Initial State:

   • result = []
   • queue = [Node(1)]

2. Level 0 (Outer loop, 1st iteration):

   • levelSize becomes 1.
   • currentLevel = [].
   • Inner loop runs once:
     • node = Node(1) is dequeued. queue is now [].
     • currentLevel becomes [1].
     • Node(2) and Node(3) are enqueued. queue is now [Node(2), Node(3)].
   • The currentLevel [1] is pushed to result. result is now [[1]].

3. Level 1 (Outer loop, 2nd iteration):

   • levelSize becomes 2.
   • currentLevel = [].
   • Inner loop runs twice:
     • i=0: node = Node(2) is dequeued. queue is now [Node(3)]. currentLevel becomes [2]. Node(4) and Node(5) are enqueued. queue is now [Node(3), Node(4), Node(5)].
     • i=1: node = Node(3) is dequeued. queue is now [Node(4), Node(5)]. currentLevel becomes [2, 3]. Node(6) and Node(7) are enqueued. queue is now [Node(4), Node(5), Node(6), Node(7)].
   • The currentLevel [2, 3] is pushed to result. result is [[1], [2, 3]].

4. Level 2 (Outer loop, 3rd iteration):

   • levelSize becomes 4.
   • currentLevel = [].
   • Inner loop runs four times, dequeuing nodes 4, 5, 6, and 7. They have no children.
   • currentLevel becomes [4, 5, 6, 7].
   • The currentLevel is pushed to result. result is now [[1], [2, 3], [4, 5, 6, 7]].

5. Termination:

   • The queue is now empty. The while loop terminates.
   • The final result is returned.

Complexity and Pitfalls

• Time Complexity: $O(N)$, where $N$ is the number of nodes. Each node is enqueued and dequeued exactly once.
• Space Complexity: $O(W)$, where $W$ is the maximum width of the tree. The space is determined by the maximum number of nodes in the queue at any one time. In the worst case (a complete, balanced binary tree), the last level can contain roughly $N/2$ nodes, making the space complexity $O(N)$.

This pattern is powerful, but small mistakes can lead to incorrect results. To solidify your understanding, it's worth reviewing common errors. The resource from Algo.monster provides an excellent breakdown of these issues.

Conclusion

In this lesson, you've added a fundamental traversal algorithm to your toolkit. While depth-first search explores vertically, breadth-first search gives you a way to explore horizontally.

Here are the key takeaways:

• Breadth-First Search (BFS) traverses a tree level by level.
• The queue data structure (FIFO) is the natural choice for implementing BFS.
• To group nodes by level (a common interview requirement), you must capture the queue's size at the start of each level and loop that many times.

So far, we have learned how to visit every node in a tree using both DFS and BFS. In our next lesson, we will build on this foundation to compute properties of a tree, such as its height, by collecting and combining information during a traversal.