Binary Tree Level Order Traversal
Return node values level by level, each level its own list.
Open on LeetCode ↗02
Intuition
A queue processes nodes in arrival order, and children arrive after parents — so the queue naturally holds one level's tail and the next level's head. Snapshot the queue length at each round: exactly that many pops belong to the current level.
03
Approach
1
BFS with a queue
Start with the root. Pop a node, record it, push its children — classic breadth-first.
2
Level boundary = queue length
Before each round, size = len(queue) is the count of the current level. Pop exactly size nodes into one sublist.
3
Children queue for the next round
Everything pushed during a round is the next level, processed in the next iteration.
04
Solution & live demo
python
▶1from collections import deque
▶2
▶3class Solution:
▶4 def levelOrder(self, root):
▶5 if not root: return []
▶6 res, q = [], deque([root])
▶7 while q:
▶8 level = []
▶9 for _ in range(len(q)):
▶10 node = q.popleft()
▶11 level.append(node.val)
▶12 if node.left: q.append(node.left)
▶13 if node.right: q.append(node.right)
▶14 res.append(level)
▶15 return res
05
Edge cases
Empty tree
No rounds → [].
Skewed tree
Every level has one node → n singleton lists.
06
Complexity
Time
O(n)
Space
O(w)
w = maximum level width.