DSA Tracker

Visualize

Binary Tree Level Order Traversal

Freeze the queue size, pop one level, enqueue the next

time O(n)space O(n) queue, worst case a full last level

A queue naturally processes nodes in the order they were discovered, which is exactly breadth-first order — but by itself it does not know where one level ends and the next begins. The trick is to read the queue's length before popping anything: that count is exactly how many nodes belong to the current level, since every child enqueued during this round is pushed to the back, after all of this level's nodes. Pop exactly that many, collect their values into one row, and whatever is left in the queue is entirely the next level.

Details

Animated on: root = [3,9,20,null,null,15,7] — return the node values grouped by depth level, top to bottom, left to right. Expected: [[3],[9,20],[15,7]].

Problem:Binary Tree Level Order TraversalMedium

Pattern:Tree BFS and Level Order

Freeze the queue size, pop one level, enqueue the next

step 1 / 15

9
3
15
20
7

Call stack

queue: [3]

Seed the queue with the root, 3. A queue gives FIFO order, so whatever goes in first (this level) comes out first — that is what keeps the levels from mixing.

Pseudocode
1FUNCTION levelOrder(root):
2  IF root = null:
3    RETURN []
4  queue <- [root]
5  WHILE queue is not empty:
6    k <- LENGTH(queue)
7    row <- []
8    FOR i <- 1 TO k:
9      node <- DEQUEUE(queue)
10      APPEND node.val TO row
11      IF node.left != null: ENQUEUE(queue, node.left)
12      IF node.right != null: ENQUEUE(queue, node.right)
13    APPEND row TO result
14  RETURN result

← / → step · space play · Home restart

Every step in words

Show all 15 steps
  1. Seed the queue with the root, 3. A queue gives FIFO order, so whatever goes in first (this level) comes out first — that is what keeps the levels from mixing.
  2. Freeze the queue's current size, k=1, before popping anything. Everything popped in the next 1 step belongs to level 0; any child enqueued during that span already belongs to level 1, and freezing k up front is what keeps the two from mixing.
  3. Dequeue 3 and append it to level 0's row: [3]. 1 of 1 popped for this level so far.
  4. 3's non-null children (9, 20) go on the back of the queue — level 1 material, never touched this round since k=1 was already fixed.
  5. Level 0 is complete: [3]. Result so far: [[3]].
  6. Freeze the queue's current size, k=2, before popping anything. Everything popped in the next 2 steps belongs to level 1; any child enqueued during that span already belongs to level 2, and freezing k up front is what keeps the two from mixing.
  7. Dequeue 9 and append it to level 1's row: [9]. 1 of 2 popped for this level so far.
  8. Dequeue 20 and append it to level 1's row: [9, 20]. 2 of 2 popped for this level so far.
  9. 20's non-null children (15, 7) go on the back of the queue — level 2 material, never touched this round since k=2 was already fixed.
  10. Level 1 is complete: [9, 20]. Result so far: [[3],[9,20]].
  11. Freeze the queue's current size, k=2, before popping anything. Everything popped in the next 2 steps belongs to level 2; any child enqueued during that span already belongs to level 3, and freezing k up front is what keeps the two from mixing.
  12. Dequeue 15 and append it to level 2's row: [15]. 1 of 2 popped for this level so far.
  13. Dequeue 7 and append it to level 2's row: [15, 7]. 2 of 2 popped for this level so far.
  14. Level 2 is complete: [15, 7]. Result so far: [[3],[9,20],[15,7]].
  15. Done: [[3],[9,20],[15,7]]. Every node is enqueued once and dequeued once, so the whole traversal costs O(n) time; the queue holds at most one level's worth of nodes, O(n) space in the worst case (a full last level).

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Binary Tree Level Order Traversal in the editorAll Binary Trees problemsBack to roadmap