Binary Tree Level Order Traversal
Problem
Given the root of a binary tree, return the level order traversal of its nodes' values as a list of lists, where each inner list contains the values of nodes at the same depth from left to right.
- The number of nodes in the tree is in the range [0, 10⁴]
- −1000 ≤ Node.val ≤ 1000
Example
root = [3,9,20,null,null,15,7][[3],[9,20],[15,7]]Starting at the root (3), the algorithm visits nodes level by level. The first level contains only 3. The second level contains 9 and 20, visited from left to right. The third level contains 15 and 7. The BFS queue initially holds the root. At each iteration, nodes currently in the queue represent one level. The algorithm dequeues each node, records its value, and enqueues its children for the next level. This process repeats until all levels are processed.
Approach
Straightforward Solution
A naive approach might attempt a depth-first traversal and then group nodes by depth afterward, which requires extra bookkeeping and is less intuitive for level order traversal.
Core Observation
Level order traversal is a classic breadth-first search (BFS) problem on trees, where nodes are visited level by level. Each level corresponds to nodes reachable in the same number of edges from the root.
Path to Optimal
The key recognition signals are 'level order' and 'nodes at the same depth', which indicate BFS traversal using a queue. BFS naturally processes nodes in layers, making it ideal for collecting nodes level by level. By enqueuing children of nodes in the current level, the algorithm prepares the next level for processing.
Optimal Approach
Use a queue initialized with the root node. While the queue is not empty, process all nodes currently in the queue (which represent one level), record their values, and enqueue their children. Append each level's values to the result list. This guarantees O(n) time and space, where n is the number of nodes.
Time
O(n)
Each node is enqueued and dequeued exactly once, resulting in linear time proportional to the number of nodes.
Space
O(n)
The queue can hold up to the maximum number of nodes at any level, which in the worst case is O(n/2) = O(n). The output list also stores all node values.
Pattern Spotlight
BFS (Level Order Traversal on Tree)
When asked to process nodes level by level in a tree, use a queue to explore nodes breadth-first, processing all nodes at the current depth before moving to the next, ensuring natural grouping by levels.
Solution
| 1 | import collections
|
| 2 |
|
| 3 | class Solution:
|
| 4 | def levelOrder(self, root: TreeNode) -> list[list[int]]:
|
| 5 | res = []
|
| 6 | if not root:
|
| 7 | return res
|
| 8 |
|
| 9 | q = collections.deque([root])
|
| 10 |
|
| 11 | while q:
|
| 12 | level = []
|
| 13 | for i in range(len(q)):
|
| 14 | node = q.popleft()
|
| 15 | level.append(node.val)
|
| 16 | if node.left:
|
| 17 | q.append(node.left)
|
| 18 | if node.right:
|
| 19 | q.append(node.right)
|
| 20 | res.append(level)
|
| 21 |
|
| 22 | return res |
| 1 | import java.util.ArrayList; |
| 2 | import java.util.List; |
| 3 | import java.util.Queue; |
| 4 | import java.util.ArrayDeque; |
| 5 | |
| 6 | class Solution { |
| 7 | public List<List<Integer>> levelOrder(TreeNode root) { |
| 8 | List<List<Integer>> res = new ArrayList<>(); |
| 9 | if (root == null) { |
| 10 | return res; |
| 11 | } |
| 12 | |
| 13 | Queue<TreeNode> q = new ArrayDeque<>(); |
| 14 | q.offer(root); |
| 15 | |
| 16 | while (!q.isEmpty()) { |
| 17 | List<Integer> level = new ArrayList<>(); |
| 18 | int size = q.size(); |
| 19 | for (int i = 0; i < size; i++) { |
| 20 | TreeNode node = q.poll(); |
| 21 | level.add(node.val); |
| 22 | if (node.left != null) { |
| 23 | q.offer(node.left); |
| 24 | } |
| 25 | if (node.right != null) { |
| 26 | q.offer(node.right); |
| 27 | } |
| 28 | } |
| 29 | res.add(level); |
| 30 | } |
| 31 | |
| 32 | return res; |
| 33 | } |
| 34 | } |
| 1 | #include <vector> |
| 2 | #include <queue> |
| 3 | |
| 4 | using namespace std; |
| 5 | |
| 6 | class Solution { |
| 7 | public: |
| 8 | vector<vector<int>> levelOrder(TreeNode* root) { |
| 9 | vector<vector<int>> res; |
| 10 | if (!root) { |
| 11 | return res; |
| 12 | } |
| 13 | |
| 14 | queue<TreeNode*> q; |
| 15 | q.push(root); |
| 16 | |
| 17 | while (!q.empty()) { |
| 18 | vector<int> level; |
| 19 | int size = q.size(); |
| 20 | for (int i = 0; i < size; ++i) { |
| 21 | TreeNode* node = q.front(); |
| 22 | q.pop(); |
| 23 | level.push_back(node->val); |
| 24 | if (node->left) { |
| 25 | q.push(node->left); |
| 26 | } |
| 27 | if (node->right) { |
| 28 | q.push(node->right); |
| 29 | } |
| 30 | } |
| 31 | res.push_back(level); |
| 32 | } |
| 33 | |
| 34 | return res; |
| 35 | } |
| 36 | }; |
| 1 | var levelOrder = function(root) { |
| 2 | const res = []; |
| 3 | if (!root) { |
| 4 | return res; |
| 5 | } |
| 6 | |
| 7 | const q = [root]; |
| 8 | let front = 0; |
| 9 | |
| 10 | while (front < q.length) { |
| 11 | const level = []; |
| 12 | const size = q.length - front; |
| 13 | for (let i = 0; i < size; i++) { |
| 14 | const node = q[front++]; |
| 15 | level.push(node.val); |
| 16 | if (node.left !== null) { |
| 17 | q.push(node.left); |
| 18 | } |
| 19 | if (node.right !== null) { |
| 20 | q.push(node.right); |
| 21 | } |
| 22 | } |
| 23 | res.push(level); |
| 24 | } |
| 25 | |
| 26 | return res; |
| 27 | }; |
Step-by-Step Solution
Initialize Result Container Before BFS Begins
| 5 | res = []
|
Objective
To create the result container that will accumulate one list of values per tree level.
Key Insight
BFS is not just about traversal order; it is also about grouping output by layer. Initializing the result container before any queue work begins makes it clear that each completed level will later be appended into this outer structure.
Interview Quick-Check
Core Logic
Create the outer result list before traversal so each finished level can be appended in order.
State & Boundaries
The result container exists even when the tree is empty, which is why the empty-tree case returns it directly.
Handle Empty Tree Edge Case
| 6 | if not root:
|
| 7 | return res
|
Objective
To immediately return an empty list if the input tree is empty, avoiding unnecessary processing.
Key Insight
Checking for an empty root upfront is critical to handle edge cases gracefully. It prevents the algorithm from initializing the queue with a null node and ensures the output matches the problem specification for empty input.
Interview Quick-Check
State & Boundaries
Return an empty list if the root is None, as there are no nodes to traverse.
Common Pitfalls & Bugs
Failing to check for an empty tree can lead to errors or incorrect output.
Initialize BFS Queue with Root Node
| 9 | q = collections.deque([root])
|
Objective
To set up the queue data structure with the root node as the starting point for BFS traversal.
Key Insight
A queue is the fundamental data structure for BFS. Initializing it with the root node ensures the traversal begins at the top of the tree. This setup enables the algorithm to process nodes level by level by dequeuing nodes and enqueuing their children.
Interview Quick-Check
Core Logic
The queue holds nodes to be processed in FIFO order, ensuring nodes are visited in breadth-first order.
Complexity
Initializing the queue with one node is O(1) time and space.
Process Each Level by Dequeuing Current Nodes and Enqueuing Children
| 11 | while q:
|
| 12 | level = []
|
| 13 | for i in range(len(q)):
|
| 14 | node = q.popleft()
|
| 15 | level.append(node.val)
|
| 16 | if node.left:
|
| 17 | q.append(node.left)
|
| 18 | if node.right:
|
| 19 | q.append(node.right)
|
| 20 | res.append(level)
|
Objective
To iterate over the tree level by level, collecting node values and preparing the next level's nodes.
Key Insight
At each iteration, the queue contains all nodes at the current level. By iterating exactly len(queue) times, the algorithm processes all nodes of that level, appends their values to a temporary list, and enqueues their children for the next level. This approach cleanly separates levels and ensures correct grouping of node values.
Interview Quick-Check
Core Logic
Processing exactly len(queue) nodes per iteration ensures that each level is handled separately and completely before moving on.
State & Boundaries
The for loop uses the snapshot length of the queue to avoid mixing nodes from different levels.
Common Pitfalls & Bugs
Modifying the queue length during iteration without using a fixed length snapshot can cause incorrect level grouping or infinite loops.
Complexity
Each node is enqueued and dequeued exactly once, maintaining O(n) time complexity.
Return the Complete List of Levels After BFS Completion
| 22 | return res |
Objective
To output the collected list of node values grouped by level after the BFS traversal finishes.
Key Insight
After the queue is empty, all nodes have been processed and their values grouped by level. Returning the accumulated result completes the traversal and provides the desired output format.
Interview Quick-Check
Core Logic
Returning the result after BFS ensures all levels are included in order.
Line Analysis
This solution has 1 Critical line interviewers watch for.
for i in range(len(q)):Iterate exactly over the number of nodes currently in the queue (current level size).
Capturing the queue length before iteration is critical to isolate nodes of the current level, preventing interference from newly enqueued child nodes and preserving level boundaries.
q = collections.deque([root])Initialize a queue with the root node to start BFS.
The queue is the core data structure for BFS, enabling level-by-level traversal by holding nodes to be processed in FIFO order.
node = q.popleft()Dequeue the next node from the queue.
Dequeuing nodes in FIFO order ensures breadth-first traversal, visiting nodes level by level.
if node.left:If the current node has a left child, enqueue it for the next level.
Adding children to the queue prepares the next level for processing, maintaining BFS order.
if node.right:If the current node has a right child, enqueue it for the next level.
Similarly, adding the right child ensures all nodes at the next depth are queued for BFS.
res.append(level)Append the current level's list of node values to the result.
Storing the collected values preserves the level grouping in the final output.
if not root:Check if the root node is None (empty tree).
This early check prevents unnecessary processing and handles the edge case where the tree has no nodes.
return resReturn an empty list if the tree is empty.
Returning immediately here ensures the function complies with the problem specification for empty input.
level.append(node.val)Append the current node's value to the level list.
Collecting node values in order preserves the left-to-right traversal order within each level.
q.append(node.left)Enqueue the left child node.
This line physically adds the left child to the queue, enabling its future processing.
q.append(node.right)Enqueue the right child node.
This line adds the right child to the queue, maintaining the BFS traversal order.
while q:Continue processing while there are nodes in the queue.
This loop ensures that all nodes are processed level by level until none remain.
return resReturn the list of levels after completing BFS traversal.
Returning the accumulated result provides the final answer as specified by the problem.
level = []Initialize a list to hold the current level's node values.
This temporary list collects values of all nodes at the current depth before appending to the result.
res = []Initialize the result list to store values of nodes level by level.
This list accumulates the final output, grouping node values by their depth in the tree.
Test Your Understanding
Why does BFS guarantee that nodes are processed level by level in a binary tree?
Because BFS uses a queue that holds all nodes at the current depth before processing their children, it processes nodes in order of increasing distance from the root, naturally grouping nodes by level.
Related Problems
BFS pattern
Don't just read it. Drill it.
Reconstruct Binary Tree Level Order Traversal from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Binary Tree Level Order Traversal drill