Language Selection
Choose your preferred programming language
Showing: Python
Level Order Traversal
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).
Examples
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
Explanation:
Level 0: [3]
Level 1: [9, 20]
Level 2: [15, 7]
Example 2:
Input: root = [1]
Output: [[1]]
Explanation: Single node tree.
Example 3:
Input: root = []
Output: []
Explanation: Empty tree.
Constraints
- The number of nodes in the tree is in the range
[0, 2000]. -1000 <= Node.val <= 1000
Approach 1: BFS with Queue (Optimal)
Algorithm
Use breadth-first search with a queue to process nodes level by level.
Steps:
- Initialize a queue with the root node
- While queue is not empty:
- Get the current level size
- Process all nodes at current level
- Add their children to queue for next level
- Return the result
Implementation
Python:
from collections import deque
def levelOrder(root):
"""
Level order traversal using BFS with queue
Time: O(n)
Space: O(w) where w is maximum width
"""
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
current_level = []
for _ in range(level_size):
node = queue.popleft()
current_level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(current_level)
return result
Java:
import java.util.*;
class Solution {
/**
* Level order traversal using BFS with queue
* Time: O(n)
* Space: O(w) where w is maximum width
*/
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
List<Integer> currentLevel = new ArrayList<>();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
currentLevel.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
result.add(currentLevel);
}
return result;
}
}
Go:
func levelOrder(root *TreeNode) [][]int {
/**
* Level order traversal using BFS with queue
* Time: O(n)
* Space: O(w) where w is maximum width
*/
if root == nil {
return [][]int{}
}
var result [][]int
queue := []*TreeNode{root}
for len(queue) > 0 {
levelSize := len(queue)
currentLevel := make([]int, 0, levelSize)
for i := 0; i < levelSize; i++ {
node := queue[0]
queue = queue[1:] // Remove first element
currentLevel = append(currentLevel, node.Val)
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
result = append(result, currentLevel)
}
return result
}
JavaScript:
/**
* Level order traversal using BFS with queue
* Time: O(n)
* Space: O(w) where w is maximum width
*/
function levelOrder(root) {
if (!root) {
return [];
}
const result = [];
const queue = [root];
while (queue.length > 0) {
const levelSize = queue.length;
const currentLevel = [];
for (let i = 0; i < levelSize; i++) {
const node = queue.shift();
currentLevel.push(node.val);
if (node.left) {
queue.push(node.left);
}
if (node.right) {
queue.push(node.right);
}
}
result.push(currentLevel);
}
return result;
}
C#:
using System.Collections.Generic;
public class Solution {
/// <summary>
/// Level order traversal using BFS with queue
/// Time: O(n)
/// Space: O(w) where w is maximum width
/// </summary>
public IList<IList<int>> LevelOrder(TreeNode root) {
var result = new List<IList<int>>();
if (root == null) {
return result;
}
var queue = new Queue<TreeNode>();
queue.Enqueue(root);
while (queue.Count > 0) {
int levelSize = queue.Count;
var currentLevel = new List<int>();
for (int i = 0; i < levelSize; i++) {
var node = queue.Dequeue();
currentLevel.Add(node.val);
if (node.left != null) {
queue.Enqueue(node.left);
}
if (node.right != null) {
queue.Enqueue(node.right);
}
}
result.Add(currentLevel);
}
return result;
}
}
Complexity Analysis
- Time Complexity: O(n) - Visit each node exactly once
- Space Complexity: O(w) - Queue stores at most one level of nodes
Key Insights
- BFS Approach: Use queue to process nodes level by level
- Level Size Tracking: Process exact number of nodes per level
- DFS Alternative: Use recursion with level parameter
- Space Trade-off: BFS uses O(w) space, DFS uses O(h) space
- Level Building: Build result level by level
Edge Cases
- Empty Tree: Return empty list
- Single Node: Return single level with one node
- Skewed Tree: Handle left-skewed or right-skewed trees
- Perfect Tree: Handle balanced trees efficiently
- Large Trees: Handle trees with many levels
Test Cases
def test_levelOrder():
# Test case 1: Normal tree
root1 = TreeNode(3)
root1.left = TreeNode(9)
root1.right = TreeNode(20)
root1.right.left = TreeNode(15)
root1.right.right = TreeNode(7)
result1 = levelOrder(root1)
expected1 = [[3], [9, 20], [15, 7]]
assert result1 == expected1
# Test case 2: Single node
root2 = TreeNode(1)
result2 = levelOrder(root2)
expected2 = [[1]]
assert result2 == expected2
# Test case 3: Empty tree
result3 = levelOrder(None)
expected3 = []
assert result3 == expected3
print("All tests passed!")
test_levelOrder()
Follow-up Questions
- Zigzag Level Order: Traverse levels in alternating directions?
- Bottom-up Level Order: Start from bottom level?
- Level Order Successor: Find next node in level order?
- Level Order Predecessor: Find previous node in level order?
- Level Order with Nulls: Include null nodes in traversal?
Common Mistakes
- Not Tracking Level Size: Forgetting to process exact number of nodes per level
- Wrong Queue Operations: Using wrong queue methods (add vs offer)
- Null Checks: Not checking for null nodes before processing
- Level Indexing: Off-by-one errors in level tracking
- Space Complexity: Confusing BFS and DFS space complexities
Interview Tips
- Start with BFS: Most intuitive approach for level order
- Explain Level Tracking: Show understanding of level size concept
- Discuss Trade-offs: Compare BFS vs DFS approaches
- Handle Edge Cases: Mention empty tree and single node cases
- Follow-up Ready: Be prepared for zigzag and other variations
Concept Explanations
BFS Approach: Breadth-first search processes nodes level by level, which naturally gives us the level order traversal. We use a queue to maintain the order of nodes to be processed.
Level Size Tracking: The key insight is to process exactly the number of nodes that are currently in the queue (which represents one level) before moving to the next level.
DFS Alternative: We can also use depth-first search by keeping track of the current level and adding nodes to the appropriate level in our result structure.
Space Complexity: BFS uses O(w) space where w is the maximum width of the tree (maximum number of nodes at any level), while DFS uses O(h) space where h is the height of the tree (recursion stack depth).
Why BFS is Preferred: BFS naturally processes nodes level by level, making it more intuitive for level order traversal. It also has better space complexity for wide trees.
Queue Operations: We use a queue to maintain the order of nodes. We enqueue children of current level nodes and dequeue nodes to process them in the correct order.