MediumBlind75TreeBFS
Binary Tree Level Order Traversal
Given the root of a binary tree, return the level order traversal of its nodes' values.
Examples
Input
root = [3,9,20,null,null,15,7]
Output
[[3],[9,20],[15,7]]
Level 0: [3], Level 1: [9,20], Level 2: [15,7]
Input
root = [1]
Output
[[1]]
Single node at level 0.
Constraints
- •
The number of nodes in the tree is in the range [0, 2000] - •
-1000 <= Node.val <= 1000
Approaches
Use DFS and track the level of each node.
CodeT: O(n) | S: O(h)
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def level_order(root):
result = []
def dfs(node, level):
if not node:
return
if level == len(result):
result.append([])
result[level].append(node.val)
dfs(node.left, level + 1)
dfs(node.right, level + 1)
dfs(root, 0)
return resultUse BFS with a queue, processing all nodes at each level.
CodeT: O(n) | S: O(n)
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def level_order(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return resultSame BFS approach with explicit queue size tracking.
Diagram
Tree: 3->9, 20->15,7
Queue: [3] -> process 3, add [9,20]
Queue: [9,20] -> process both, add [15,7]
Result: [[3],[9,20],[15,7]]
CodeT: O(n) | S: O(n)
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def level_order(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level = []
level_size = len(queue)
for _ in range(level_size):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return resultComplexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| DFS with Level Tracking | O(n) | O(h) | Use DFS and track the level of each node. |
| BFS - Queue | O(n) | O(n) | Use BFS with a queue, processing all nodes at each level. |
| BFS - Optimized Queue | O(n) | O(n) | Same BFS approach with explicit queue size tracking. |
DFS with Level Tracking
T: O(n)S: O(h)
Use DFS and track the level of each node.
BFS - Queue
T: O(n)S: O(n)
Use BFS with a queue, processing all nodes at each level.
BFS - Optimized Queue
T: O(n)S: O(n)
Same BFS approach with explicit queue size tracking.
Common Mistakes
Not using the queue size to separate levels
Adding children to the result before processing the current level
Forgetting to handle the empty tree case