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 <= 1000The key idea behind Binary Tree Level Order Traversal is to process nodes level by level, starting from the root and moving downward. The most efficient strategy uses Breadth-First Search (BFS) with a queue. BFS naturally explores nodes in layers, which aligns perfectly with the requirement to group nodes by their depth in the tree.
You begin by pushing the root node into a queue. For each iteration, process all nodes currently in the queue—these represent a single level. While processing them, collect their values and push their left and right children into the queue for the next level. This ensures nodes are visited in the exact order required for level-wise traversal.
An alternative idea is to use Depth-First Search (DFS) with recursion while tracking the current depth and storing values in a list corresponding to that level. However, BFS is generally the most intuitive and commonly used approach for this problem. The traversal touches each node exactly once, giving efficient performance.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Breadth-First Search (Queue) | O(n) | O(n) |
| Depth-First Search with Level Tracking | O(n) | O(n) |
take U forward
Use these hints if you're stuck. Try solving on your own first.
Use a queue to perform BFS.
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.
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.
1import java.util.ArrayList;
2import java.util.LinkedList;
3import java.util.List;
4import java.util.Queue;
5
6class TreeNode {
7 int val;
8 TreeNode left;
9 TreeNode right;
10 TreeNode() {}
11 TreeNode(int val) { this.val = val; }
12 TreeNode(int val, TreeNode left, TreeNode right) {
13 this.val = val;
14 this.left = left;
15 this.right = right;
16 }
17}
18
19public class Solution {
20 public List<List<Integer>> levelOrder(TreeNode root) {
21 List<List<Integer>> levels = new ArrayList<>();
22 if (root == null) return levels;
23 Queue<TreeNode> queue = new LinkedList<>();
24 queue.add(root);
25 while (!queue.isEmpty()) {
26 int levelSize = queue.size();
27 List<Integer> level = new ArrayList<>();
28 for (int i = 0; i < levelSize; i++) {
29 TreeNode node = queue.poll();
30 level.add(node.val);
31 if (node.left != null) queue.add(node.left);
32 if (node.right != null) queue.add(node.right);
33 }
34 levels.add(level);
35 }
36 return levels;
37 }
38}Utilizing Java's ArrayList for dynamic arrays and LinkedList as the queue, this solution processes the binary tree by levels. After checking that the root is not null, while the queue isn’t empty, iterate over each level, collecting node values and adding children to the queue for subsequent levels. Append each level's results to the overall list, which is returned at the end.
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.
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.
1#include <vector>
2using namespace std;
3
4struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
void dfs(TreeNode* node, int level, vector<vector<int>>& levels) {
if (!node) return;
if (level == levels.size())
levels.push_back(vector<int>());
levels[level].push_back(node->val);
dfs(node->left, level + 1, levels);
dfs(node->right, level + 1, levels);
}
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> levels;
dfs(root, 0, levels);
return levels;
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, it can also be solved using Depth-First Search by keeping track of the current depth during recursion. You store node values in a list corresponding to their level. However, BFS is typically simpler and more intuitive for this problem.
Yes, this problem or its variations frequently appear in FAANG and other top tech company interviews. It tests understanding of tree traversal, BFS, and queue-based problem solving.
A queue is the most suitable data structure because it supports the FIFO order required for Breadth-First Search. By pushing child nodes into the queue as you process the current level, you naturally traverse the tree layer by layer.
The optimal approach uses Breadth-First Search (BFS) with a queue. BFS processes nodes level by level, making it ideal for collecting values from each tree level in order. Each node is visited once, resulting in O(n) time complexity.
Invoke the DFS function recursively by starting at the root node. We use a vector of vectors to represent levels during traversal. For each visited node, determine the current level size and append values to their respective level container, expanding the container list when necessary. Recurse into children while maintaining depth count to achieve the level order.