0

Level Order Traversal

Medium

Process the queue one full level at a time by snapshotting its length before the inner loop.

queueBFS
TimeO(n)
SpaceO(width)
InputLevel order values
3
9
20
1
2
15
7
queue
3

Put the root in the queue.

1 / 15
queue = [root]
while queue:
size = queue.length // snapshot one level
for i in 0..size-1:
node = queue.pop_front()
push node.left and node.right
Why it matters

This single trick powers right side view, zigzag, minimum depth and average of levels.

Practise this
Binary Tree Level Order TraversalMBinary Tree Right Side ViewMBinary Tree Zigzag Level Order TraversalM
Keyboard
space play← → stepr restartctrl K search

More in Trees

Tree Traversals (Pre / In / Post)
O(n)
Next visualiser
BST Insert & Search