Binary Tree Level Order Traversal II
Binary Tree Level Order Traversal II: return the values of a binary tree level by level, ordered from the deepest level up to the root.
- The number of nodes in the tree is in the range [0, 2000]
- -1000 <= Node.val <= 1000
Intuition
A queue naturally produces levels top-down, and no traversal produces them bottom-up directly — you cannot know which level is deepest until the tree is exhausted. So collect levels the usual way and reverse the result. The only real technique is processing the queue one level at a time by snapshotting its size before the level begins, which keeps each level's values grouped instead of flattened into a single stream.
Any question about levels, depth, or shortest distance in an unweighted structure wants breadth-first search, and any question grouping results by level wants the size snapshot. Binary Tree Right Side View, Average of Levels, and Zigzag Level Order are the same loop with a different per-level reduction.
Approach
Before reading on: work out what separates one level from the next inside a single shared queue. Then decide whether to reverse at the end or insert at the front, and what each costs.
Snapshot the queue size to slice levels apart
A breadth-first queue mixes levels: while draining level d, the children of level d + 1 are being pushed onto the same queue. The separator is the queue's length at the moment the level starts. Record count = len(queue) before the inner loop, then pop exactly count nodes — those are precisely the nodes of the current level, because every later push belongs to the next one. Without this snapshot the traversal still visits every node in the right order but loses the level boundaries entirely.
Why bottom-up must be built top-down first
The deepest level cannot be identified until the whole tree has been walked, so there is no way to emit it first. Every correct solution therefore builds the levels top-down and reverses at the end. Two options exist: append each level and reverse once at the finish, or insert each level at the front as it completes. Appending then reversing is O(n) overall, while front-insertion costs O(d) per level as the existing entries shift, making it O(d²) in the number of levels — the same answer for more work.
Children are enqueued left before right
Within a level the values must read left to right, which is inherited from the order children are pushed. Enqueue node.left before node.right, and the queue preserves that ordering into the next level automatically — a queue's FIFO discipline is doing the work. Reversing the outer list at the end flips the order of levels, not the order within them, so the left-to-right reading survives. Time is O(n) with each node enqueued and dequeued exactly once, and space is O(w) where w is the widest level.
Solution & live demo
Common pitfalls
Not snapshotting the queue size
while queue:
node = queue.popleft()
current.append(node.val)count = len(queue)
for _ in range(count):
node = queue.popleft()Reading len(queue) inside the loop sees it grow as children are pushed, so the level never ends and all nodes collapse into one flat list. The size must be fixed before the level begins.
Returning [[]] for an empty tree
if not root:
return [[]]if not root:
return []An empty tree has zero levels, not one empty level. Returning a list containing an empty list reports a level that does not exist.
Inserting each level at the front
levels.insert(0, current)
levels.append(current) ... return levels[::-1]
Each front-insertion shifts every existing level, costing O(d) per level and O(d²) overall. Appending and reversing once is linear and produces the identical result.
Edge cases
The queue never starts, so an empty list is returned rather than [[]].
One level containing the root; reversing a one-element list changes nothing.
Every level holds one node, and the output is the chain read from the bottom up.
Level sizes double, and the size snapshot keeps each level intact.
The None left child is never enqueued, so no empty slot appears in the level.