Level-Order Tree Traversal with Queues

What is Level-Order Traversal?

Level-order traversal means visiting all the nodes at a given level from left to right, before moving on to the nodes at the next level.

Consider this binary tree:

The resulting traversal would be: 5, 2, 8, 1, 4, 6, 9, 11.

The Algorithm: Using a Queue for Breadth-First Search

To visit nodes level by level, we need a data structure that processes elements in the order they are added. This is a perfect use case for a Queue, which operates on a First-In, First-Out (FIFO) basis.

The core idea is:

1. Start with the root node. Add it to a queue.
2. While the queue is not empty, process all the nodes currently in it. These nodes constitute a single level.
3. For each node you process, add its children (left, then right) to the queue. These children will form the next level to be processed.

To see this process in action, the following video provides an excellent visual walkthrough.

As the video explained, the clever trick to group nodes by level is to get the queue's size before you start processing the level. This size tells you exactly how many nodes are on the current level, allowing you to iterate through them and add their children for the next level without mixing them up.

Java Implementation

Now, let's translate this logic into Java code. For the tree nodes, we'll use the same TreeNode class from the previous lesson. The problem is often framed to return a list of lists, where each inner list contains the node values for one level.

We'll use the code from the takeuforward.org tutorial as our reference.

Here is the core logic, broken down and explained:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

// Assuming the TreeNode class is defined as in the previous lesson.
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        // The final list that will hold all the levels.
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans; // Handle the edge case of an empty tree.
        }

        // In Java, Queue is an interface. LinkedList is a common class that implements it.
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);

        // Continue as long as there are nodes to process.
        while (!q.isEmpty()) {
            // 1. Get the number of nodes at the current level.
            int levelSize = q.size();
            List<Integer> currentLevel = new ArrayList<>();

            // 2. Process exactly that many nodes.
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = q.poll(); // Dequeue the next node in the level.
                currentLevel.add(node.data);

                // 3. Enqueue children for the next level.
                if (node.left != null) {
                    q.add(node.left);
                }
                if (node.right != null) {
                    q.add(node.right);
                }
            }
            // 4. Add the completed level to the final answer.
            ans.add(currentLevel);
        }
        return ans;
    }
}

This implementation is robust and efficient, making it a standard solution you should be very comfortable with for interviews.

Complexity Analysis

Understanding the performance of your algorithms is critical.

• Time Complexity: O(N), where N is the number of nodes in the tree. Every node is enqueued and dequeued exactly once.
• Space Complexity: O(W), where W is the maximum width of the binary tree. The space is determined by the maximum number of nodes the queue holds at any given time, which corresponds to the widest level of the tree. In a complete binary tree, the last level contains roughly N/2 nodes, making the worst-case space complexity O(N).

public List<Double> averageOfLevels(TreeNode root) {
    List<Double> result = new ArrayList<>();
    if (root == null) return result;

    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);

    while (!q.isEmpty()) {
        int levelSize = q.size();
        double levelSum = 0.0; // Use a double for the sum to maintain precision.

        for (int i = 0; i < levelSize; i++) {
            TreeNode node = q.poll();
            levelSum += node.data;

            if (node.left != null) q.add(node.left);
            if (node.right != null) q.add(node.right);
        }
        
        result.add(levelSum / levelSize); // Calculate and add the average.
    }
    return result;
}

Conclusion

Today you've mastered level-order traversal, a fundamental breadth-first search (BFS) algorithm for trees. This contrasts with the depth-first search (DFS) strategies (preorder, inorder, postorder) from our previous lesson.

Key Takeaways:

• Breadth-First vs. Depth-First: Level-order traversal explores the tree layer by layer, whereas DFS goes deep down a branch before exploring siblings.
• The Right Tool: A Queue (FIFO) is the essential data structure for level-order traversal, ensuring nodes are processed in the order they are discovered.
• The "Level Size" Technique: Capturing the queue's size before the inner loop is the key to processing nodes one level at a time and collecting level-specific results.
• Complexity: The algorithm is efficient, with O(N) time complexity and O(N) worst-case space complexity.

Preview of the next lesson:
Now that you're comfortable with both depth-first and breadth-first traversals, we'll see how to apply and adapt these techniques to solve common problems. In the next lesson, we'll learn how to calculate the height, diameter, and size of a binary tree, which are classic problems that often build directly on the traversal logic you've learned.