Watch 10 video solutions for Binary Tree Level Order Traversal, a medium level problem involving Tree, Breadth-First Search, Binary Tree. This walkthrough by take U forward has 490,308 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |