Watch 10 video solutions for Binary Tree Level Order Traversal, a medium level problem involving Tree, Breadth-First Search, Binary Tree. This walkthrough by NeetCode has 273,172 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 level by level from left to right. Each level should appear as a separate list in the final result.
Approach 1: Breadth-First Search Using Queue (O(n) time, O(w) space)
This problem naturally fits Breadth-First Search. Use a queue to process nodes level by level. Start by pushing the root node into the queue. For each iteration, record the current queue size because it represents the number of nodes at that level. Dequeue exactly that many nodes, append their values to the current level list, and push their left and right children into the queue. Continue until the queue is empty. Every node is visited exactly once, so the time complexity is O(n). The queue can hold up to the width of the tree, giving O(w) auxiliary space in the worst case.
This approach mirrors the conceptual definition of level order traversal. Because nodes are processed in the same order they appear by depth, the implementation stays simple and predictable. When working with tree traversal problems that require grouping nodes by depth, BFS is usually the first algorithm to consider.
Approach 2: Depth-First Search with Precomputed Levels (O(n) time, O(h) space)
A binary tree can also be traversed using DFS while tracking the current depth. During recursion, pass the level index as a parameter. If the result list does not yet contain a list for that depth, create one. Then append the current node's value to result[level]. Recursively process the left child and then the right child with level + 1.
This method still visits each node exactly once, so the runtime remains O(n). The recursion stack grows to the tree height h, giving O(h) auxiliary space (excluding the output). DFS is useful when the problem already requires recursive traversal or when you want tighter control over recursion logic. The tradeoff is that level grouping must be handled manually using the depth index.
Recommended for interviews: The BFS queue approach is what interviewers usually expect first. Level order traversal is essentially BFS applied to a tree, so recognizing that mapping quickly demonstrates algorithmic intuition. Showing the DFS-with-level-index variant afterward demonstrates deeper understanding of tree traversal patterns and flexibility in implementation.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search Using Queue | O(n) | O(w) | Standard level order traversal; easiest and most intuitive solution |
| Depth-First Search with Level Index | O(n) | O(h) | Useful when implementing recursive tree traversals or when DFS structure is preferred |