Binary Tree Level Order Traversal - Solution & Explanation
Problem Statement
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:
- The number of nodes in the tree is in the range
[0, 2000]. -1000 <= Node.val <= 1000
Approach Overview
Problem 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 1: Breadth-First Search Using Queue
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.
Code
Python
JavaScript
Java
Complexity
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.
Approach 2: Depth-First Search (DFS) with Precomputed Levels
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.
Complexity
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 3: BFS
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:
- Traverse all nodes in the current queue, store their values in a temporary array
t, and then enqueue their child nodes. - Store the temporary array
tin 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.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Binary Tree Level Order Traversal - BFS - Leetcode 102 • NeetCode • 286,074 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Binary Tree Level Order Traversal easy or hard?
Binary Tree Level Order Traversal Python/Java solution
How to solve Binary Tree Level Order Traversal in O(n)?
What is the best approach for Binary Tree Level Order Traversal?
Is Binary Tree Level Order Traversal asked at Google/Amazon/Meta?
What data structure is used in Binary Tree Level Order Traversal?
What is the time complexity of Binary Tree Level Order Traversal?
Ready to solve this problem?
Practice Binary Tree Level Order Traversal with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor