Problem Statement
Given the root of a binary tree, return its level order traversal.
Nodes should be traversed:
Level by Level
↓
Left to Right
Brute Force Intuition
In an interview, you can explain it like this:
Find the height of the tree. Then, for every level, recursively print all nodes at that level.
Although correct, every level requires traversing the tree again, leading to unnecessary repeated work.
Complexity
- Time Complexity: O(N²) (Worst Case - Skewed Tree)
- Space Complexity: O(H)
Brute Force Code
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
int height = getHeight(root);
for (int i = 1; i <= height; i++) {
List<Integer> level = new ArrayList<>();
printLevel(root, i, level);
ans.add(level);
}
return ans;
}
private int getHeight(TreeNode root) {
if (root == null)
return 0;
return 1 + Math.max(
getHeight(root.left),
getHeight(root.right));
}
private void printLevel(TreeNode root,
int level,
List<Integer> list) {
if (root == null)
return;
if (level == 1) {
list.add(root.val);
return;
}
printLevel(root.left,
level - 1,
list);
printLevel(root.right,
level - 1,
list);
}
}
Moving Towards the Optimal Approach
Notice that we don't need to repeatedly traverse the tree.
Instead,
process nodes exactly in the order they appear:
Level by Level
This is exactly what:
Breadth First Search (BFS)
does.
Pattern Recognition
Whenever you see:
- Level Order Traversal
- Minimum Levels
- Process Tree Level Wise
Think:
Queue + BFS
Key Observation
Use a queue.
Initially:
Queue
↓
Root
For every level:
size = queue.size();
Process exactly:
size Nodes
These nodes belong to the current level.
Their children become the next level.
Optimal Approach
Step 1
Push the root into the queue.
Step 2
For every level:
size = queue.size();
Step 3
Process all nodes of the current level.
Store them into a list.
Step 4
Push:
Left Child
↓
Right Child
into the queue.
Optimal Java Solution
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null)
return ans;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode curr = q.poll();
level.add(curr.val);
if (curr.left != null)
q.offer(curr.left);
if (curr.right != null)
q.offer(curr.right);
}
ans.add(level);
}
return ans;
}
}
Dry Run
3
/ \
9 20
/ \
15 7
Level 1
Queue:
3
Output:
[3]
Level 2
Queue:
9
20
Output:
[9,20]
Level 3
Queue:
15
7
Output:
[15,7]
Final Answer:
[
[3],
[9,20],
[15,7]
]
Why BFS Works?
A queue follows:
FIFO
Nodes are processed in the exact order they are discovered.
Processing one queue size at a time naturally separates the traversal into individual levels.
Complexity Analysis
| Metric | Complexity |
|---|---|
| Time Complexity | O(N) |
| Space Complexity | O(N) |
Interview One-Liner
Perform a breadth-first traversal using a queue, processing one level at a time by iterating over the current queue size.
Pattern Learned
Queue
↓
Process One Level
↓
Push Children
↓
Repeat
Similar Problems
- Binary Tree Level Order Traversal
- Zigzag Level Order Traversal
- Left View of Binary Tree
- Right View of Binary Tree
- Maximum Width of Binary Tree
- Average of Levels in Binary Tree
Memory Trick
Think:
Queue
↓
Current Level Size
↓
Process Nodes
↓
Push Children
↓
Next Level
Mental Model
Root
↓
Queue
↓
One Level
↓
Next Level
↓
Repeat
Whenever you hear:
"Traverse the tree level by level"
your brain should immediately think:
Breadth First Search (BFS) + Queue
Top comments (0)