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.
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.
Python
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.
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.
We can use the BFS method to solve this problem. First, enqueue the root node, then continuously perform the following operations until the queue is empty:
t, and then enqueue their child nodes.t in the answer array.Finally, return the answer array.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| 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. |
| BFS | — |
| 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 |
Binary Tree Level Order Traversal - BFS - Leetcode 102 • NeetCode • 273,172 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