Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).
Example 1:
Input: root = [3,9,20,null,null,15,7] Output: [[3],[9,20],[15,7]]
Example 2:
Input: root = [1] Output: [[1]]
Example 3:
Input: root = [] Output: []
Constraints:
[0, 2000].-1000 <= Node.val <= 1000Problem Overview: Given the root of a binary tree, return the node values grouped by level from top to bottom. Each level should appear as a separate list, representing the nodes encountered during a level-by-level traversal.
Approach 1: Breadth-First Search Using Queue (O(n) time, O(n) space)
This approach performs a classic Breadth-First Search across the tree. Start by pushing the root node into a queue. For each iteration, process all nodes currently in the queue (which represent one level), record their values, and push their left and right children back into the queue. The key insight is that the queue naturally preserves traversal order, so nodes are visited level by level without extra bookkeeping. This method works for any binary tree structure and guarantees that each node is visited exactly once.
During each loop iteration, capture the queue size first. That number represents how many nodes belong to the current level. Iterate exactly that many times, collect values, and enqueue children for the next level. Since each node enters and leaves the queue once, the traversal runs in O(n) time. The queue can hold up to an entire tree level in the worst case, giving O(n) auxiliary space.
Approach 2: Depth-First Search with Precomputed Levels (O(n) time, O(h) space)
This solution uses recursion with tree traversal instead of a queue. Perform a DFS while tracking the current depth. When visiting a node, check whether a list already exists for that depth. If not, create one. Append the node value to the list corresponding to its level, then recursively process the left and right children with level + 1. The insight is that DFS can simulate level grouping by storing nodes according to depth during traversal.
Each node is still processed once, giving O(n) time complexity. Space usage depends on recursion depth, which is O(h) where h is the tree height (up to O(n) for skewed trees). This version is useful if your environment favors recursion or when integrating with other DFS-based tree algorithms.
Recommended for interviews: The queue-based BFS solution is what most interviewers expect. It directly models level traversal and clearly demonstrates understanding of BFS on trees. Showing the DFS-with-level-index variant demonstrates deeper flexibility with recursion, but BFS is typically considered the canonical solution.
This approach utilizes a queue to perform a Breadth-First Search (BFS) on the binary tree. Starting from the root, traverse each level of the tree and store values of nodes in separate lists for each level. By using a queue, we can efficiently keep track of nodes at the current level and their respective children for the next level.
We use a deque from the collections module to easily append and pop nodes from the queue. Starting with the root node if it is not null, we add it to the queue. For each level, determine the number of nodes at that level (i.e., the size of the queue), then iterate over them, adding each node's children to the queue for the next level. Collect and return the node values in a nested list representing each level.
JavaScript
Java
Time Complexity: O(n), where n is the number of nodes in the tree because each node is visited once.
Space Complexity: O(n), as we store all nodes at each level in the queue.
This approach involves using a Depth-First Search (DFS) where we pass along the current level during the recursive calls. By keeping track of the current depth, we can directly add node values to their appropriate level in our result list, creating new levels in our result list as needed.
This C implementation makes use of recursive DFS calls. Starting with an empty result array, we traverse the tree. For each node, check if the current level is present in the result array. If not, allocate space for a new level's data. Store node values at their respective levels and recurse into children, incrementing the level parameter. This allows us to collect all nodes according to their levels in the tree.
C++
C#
Time Complexity: O(n) since each node is visited once.
Space Complexity: O(n), considering the space needed for the result and recursive call stack.
| Approach | Complexity |
|---|---|
| Breadth-First Search Using Queue | Time Complexity: O(n), where n is the number of nodes in the tree because each node is visited once. |
| Depth-First Search (DFS) with Precomputed Levels | Time Complexity: O(n) since each node is visited once. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search Using Queue | O(n) | O(n) | Standard approach for level order traversal; most intuitive and commonly expected in interviews |
| Depth-First Search with Level Tracking | O(n) | O(h) | Useful when recursion is preferred or when integrating with other DFS-based tree algorithms |
L8. Level Order Traversal of Binary Tree | BFS | C++ | Java • take U forward • 490,308 views views
Watch 9 more video solutions →Practice Binary Tree Level Order Traversal with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor