Binary Tree Level Order Traversal

LeetCode 102: Binary Tree Level Order Traversal Solution & Explanation

Problem Overview

TL;DR: Use a Queue and a Breadth-First Search (BFS) approach to process nodes row by row, capturing the queue size at the start of each level to distinguish between depths.

The Binary Tree Level Order Traversal problem requires us to visit every node in a binary tree and group their values according to their depth. The output must be a list of lists, where the first list contains the root, the second contains the root's children, the third contains the grandchildren, and so on. This is a fundamental tree operation often tested in technical interviews and serves as the basis for many complex graph algorithms.

Brute Force Approach for Binary Tree Level Order Traversal

A naive or brute force approach to solving LeetCode 102 might involve attempting to collect nodes level by level without utilizing a queue-based structure efficiently.

One such method is to determine the height of the tree first, and then perform a separate traversal for every single level.

Pseudo-code:

1. Calculate the height $H$ of the tree.
2. Loop from $i = 0$ to $H$:
3. Call a helper function getNodesAtLevel(root, current_level, target_level) that performs a DFS.
4. If current_level == target_level, add the node to the list.
5. Otherwise, recurse to children.

Time Complexity: $O(N^2)$ in the worst case (a skewed tree). For a balanced tree, it is roughly $O(N \log N)$. Why it fails: While this approach does not strictly fail correctness tests, it is highly inefficient. We traverse the upper levels of the tree repeatedly to reach the lower levels. In a professional interview setting, an $O(N^2)$ solution for a linear traversal problem is considered suboptimal and demonstrates a lack of understanding of standard traversal patterns.

Algorithm Strategy: Tree Traversal Patterns (DFS & BFS)

1. Initialization: Check if the root is null. If so, return an empty list. Initialize a Queue and add the root. Initialize a result list to hold the list of levels.
2. BFS Loop: Continue strictly while the queue is not empty.
3. Level Processing:
   • Determine levelSize by reading the current size of the queue.
   • Create a currentLevel list to store values for this depth.
   • Start a for loop that runs exactly levelSize times.
4. Node Expansion:
   • Inside the inner loop, dequeue the front node.
   • Add its value to currentLevel.
   • If the node has a left child, enqueue it.
   • If the node has a right child, enqueue it.
5. Aggregation: After the inner loop finishes (meaning one full level is processed), add currentLevel to result.
6. Termination: Return result when the queue is empty.

Execution Flow

Let's trace the algorithm with Input: root = [3,9,20,null,null,15,7].

1. Setup: Queue Q = [3]. Result Res = [].
2. First Pass:
   • Q is not empty.
   • levelSize = 1.
   • Inner Loop (1 iter):
     • Dequeue 3. currentLevel = [3].
     • Enqueue 9 (left). Enqueue 20 (right).
   • End Inner Loop. Q = [9, 20].
   • Add [3] to Res. Res = [[3]].
3. Second Pass:
   • Q is not empty.
   • levelSize = 2.
   • Inner Loop (2 iters):
     • Iter 1: Dequeue 9. currentLevel = [9]. No children.
     • Iter 2: Dequeue 20. currentLevel = [9, 20]. Enqueue 15, 7.
   • End Inner Loop. Q = [15, 7].
   • Add [9, 20] to Res. Res = [[3], [9, 20]].
4. Third Pass:
   • Q is not empty.
   • levelSize = 2.
   • Inner Loop (2 iters):
     • Iter 1: Dequeue 15. currentLevel = [15]. No children.
     • Iter 2: Dequeue 7. currentLevel = [15, 7]. No children.
   • End Inner Loop. Q = [].
   • Add [15, 7] to Res. Res = [[3], [9, 20], [15, 7]].
5. End: Queue is empty. Return Res.

Proof of Correctness

The correctness relies on the FIFO property of the queue and the loop invariant regarding levelSize.

• Invariant: At the start of the outer while loop, the queue contains only nodes at depth $D$.
• Base Case: At depth 0, the queue contains only the root.
• Inductive Step: Suppose the queue contains all nodes at depth $D$. By iterating exactly levelSize times, we process every node at depth $D$. For each node, we enqueue its children (depth $D+1$). Since new nodes are added to the back, they are not processed in the current inner loop.
• Conclusion: Once the inner loop finishes, all nodes of depth $D$ are removed, and all nodes of depth $D+1$ are in the queue. The order is preserved left-to-right because we enqueue left children before right children.

Pattern Reuse Notes

The Tree BFS - Level Order Traversal pattern is highly reusable. Mastering the queue-size snapshot technique allows you to solve several related LeetCode problems efficiently:

• LeetCode 103: Binary Tree Zigzag Level Order Traversal: Identical to this problem, but you reverse the currentLevel list every other iteration.
• LeetCode 199: Binary Tree Right Side View: Perform the same traversal, but only add the last element of currentLevel to your result.
• LeetCode 515: Find Largest Value in Each Tree Row: Instead of collecting all nodes, track the maximum value seen in the inner loop for each level.
• LeetCode 1161: Maximum Level Sum of a Binary Tree: Sum the values in the inner loop and track which level produces the highest sum.

Reference Implementation

C++ Solution for LeetCode 102

1#include <vector>
2#include <queue>
3
4using namespace std;
5
6struct TreeNode {
7    int val;
8    TreeNode *left;
9    TreeNode *right;
10    TreeNode() : val(0), left(nullptr), right(nullptr) {}
11    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
12    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
13};
14
15class Solution {
16public:
17    vector<vector<int>> levelOrder(TreeNode* root) {
18        vector<vector<int>> result;
19        if (!root) {
20            return result;
21        }
22
23        queue<TreeNode*> q;
24        q.push(root);
25
26        while (!q.empty()) {
27            int levelSize = q.size();
28            vector<int> currentLevel;
29
30            for (int i = 0; i < levelSize; ++i) {
31                TreeNode* node = q.front();
32                q.pop();
33
34                currentLevel.push_back(node->val);
35
36                if (node->left) {
37                    q.push(node->left);
38                }
39                if (node->right) {
40                    q.push(node->right);
41                }
42            }
43            result.push_back(currentLevel);
44        }
45
46        return result;
47    }
48};

Java Solution for LeetCode 102

1import java.util.ArrayList;
2import java.util.LinkedList;
3import java.util.List;
4import java.util.Queue;
5
6class TreeNode {
7    int val;
8    TreeNode left;
9    TreeNode right;
10    TreeNode() {}
11    TreeNode(int val) { this.val = val; }
12    TreeNode(int val, TreeNode left, TreeNode right) {
13        this.val = val;
14        this.left = left;
15        this.right = right;
16    }
17}
18
19class Solution {
20    public List<List<Integer>> levelOrder(TreeNode root) {
21        List<List<Integer>> result = new ArrayList<>();
22        if (root == null) {
23            return result;
24        }
25
26        Queue<TreeNode> queue = new LinkedList<>();
27        queue.offer(root);
28
29        while (!queue.isEmpty()) {
30            int levelSize = queue.size();
31            List<Integer> currentLevel = new ArrayList<>();
32
33            for (int i = 0; i < levelSize; i++) {
34                TreeNode node = queue.poll();
35                currentLevel.add(node.val);
36
37                if (node.left != null) {
38                    queue.offer(node.left);
39                }
40                if (node.right != null) {
41                    queue.offer(node.right);
42                }
43            }
44            result.add(currentLevel);
45        }
46
47        return result;
48    }
49}

Python Solution for LeetCode 102

1from collections import deque
2from typing import List, Optional
3
4# Definition for a binary tree node.
5class TreeNode:
6    def __init__(self, val=0, left=None, right=None):
7        self.val = val
8        self.left = left
9        self.right = right
10
11class Solution:
12    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
13        result = []
14        if not root:
15            return result
16        
17        # Initialize queue with root
18        queue = deque([root])
19        
20        while queue:
21            level_size = len(queue)
22            current_level = []
23            
24            # Process strictly the nodes at the current level
25            for _ in range(level_size):
26                node = queue.popleft()
27                current_level.append(node.val)
28                
29                if node.left:
30                    queue.append(node.left)
31                if node.right:
32                    queue.append(node.right)
33            
34            result.append(current_level)
35            
36        return result