Pattern visualizer

Binary Tree Level Order Traversal

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. 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]]..

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

time O(n)space O(n) queue, worst case a full last levelstep 1 / 15

Call stack

queue: [3]

line 4

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

Where to practice Binary Trees

Practice Binary Trees problems All Binary Trees problems Back to roadmap