LESSON 16 · PATTERN GUIDE

Tree BFS / Level Order

Use a queue to visit tree nodes in layers, from the root outward.

FIRST, LEARN THE PATTERNBreadth-first search processes all nodes at a depth before moving to the next depth. Queue size at the start of a round identifies one level.

The task asks for level order, values by depth, nearest node, or the first level satisfying a condition.

How to approach it

Push the root, then repeatedly process the current queue length and enqueue each node's children.

Watch out for

Queue memory can grow with the widest level; do not use a stack if exact level order matters.

A CLOSER EXPLANATION

A queue preserves the order nodes were discovered, which naturally visits a tree by distance from the root. Capture the queue length before processing a level so newly discovered children are saved for the next round. BFS is useful when the nearest solution is required in an unweighted tree.

NOW YOU TRY

Practice question

What is the level-order traversal of a tree with root 1, children 2 and 3, and node 2's right child 4?

EXAMPLETree levels: [1], [2, 3], [4]Give your answer before revealing the explanation.

Show a hint

Process the queue one level at a time.

Show an answer

[[1], [2, 3], [4]]

CONNECT IT TO REAL LIFE

Tree BFS / Level Order at work

A building directory is a hierarchy. Starting at the lobby, list departments floor by floor, with all departments at the same depth together. Which traversal matches this?

Show one possible approach

Breadth-first search with a queue. Process exactly the current queue length for each floor/level, then process the children in the next round.

Practice next

Use these problem IDs to find additional practice for this pattern:

102103199515637116