</> MAANG.io
Sign in
Level101201301
coding interview · 101

Foundations

Master coding interviews with comprehensive coverage of data structures, algorithms, and problem-solving techniques. Progress from fundamentals to advanced topics with expertly curated content.

0/255 solved 0% complete

BFS on Trees

What is this?

Breadth-first search visits a tree one whole layer at a time: first the top node, then everyone one step away, then everyone two steps away, and so on — like ripples spreading out from a stone dropped in a pond. Because it always finishes the nearer ring before moving farther out, the very first time it reaches your goal, it got there in the fewest possible steps. That makes it the go-to tool whenever a question asks for the shortest or fewest of anything.

flowchart TD A["Put the start node in a queue"] --> B["Take the front node"] B --> C["Visit it"] C --> D["Add its neighbors to the back"] D --> E["Repeat one full ring at a time"]

💡 Fun fact: This same ripple logic is exactly how GPS and network routers find shortest routes, and how social apps figure out your degrees of separation from someone else.

🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

Core idea: Breadth-first search processes nodes level by level, which makes it the tool for two jobs: reading a tree by depth (level-order), and finding the fewest steps to reach a goal. Because BFS expands outward one ring at a time, the first time it reaches a target, it has reached it by the shortest path — a guarantee DFS cannot make.

Two uses of BFS

Two uses of BFS: level-order (queue, one full level per round, per-level summaries) and shortest path (each move is one edge in an implicit graph, first hit = fewest moves)

The second use is the powerful one: when states aren't tree nodes but configurations (a string with deletions, a car's (position, speed)), BFS over those states finds the minimum number of moves.

The problems

BFS expand level by level branches into level-order on a real tree (Right Side View, last per level) and shortest moves in a state graph (Remove Invalid Parentheses, fewest deletions; Race Car, fewest instructions)

  • Binary Tree Right Side View — classic level-order: take the last node of each BFS level (a left node can be visible if the right side is shorter).
  • Remove Invalid Parentheses — BFS over strings by number of deletions; the first valid level holds all minimum-removal answers.
  • Race Car — BFS over (position, speed) states; BFS layers count instructions, so the first time the target is dequeued is optimal.

Key takeaways

  • BFS = level-by-level, powered by a queue.
  • First reach = shortest path — the reason to pick BFS over DFS for "fewest steps."
  • States can be more than tree nodes — model strings/configurations as an implicit graph and BFS over it.
  • Stop at the first goal level — going deeper can only cost more moves.
  • Why interviewers love it: recognizing "fewest steps ⇒ BFS over states" separates pattern-matchers from problem-solvers.

Order: Right Side View → Remove Invalid Parentheses → Race Car.

Race Car

Core idea: Every reachable (position, speed) is a node; pressing 'A' or 'R' is an edge to a neighbor. The shortest instruction sequence is the shortest path from (0, 1) to any state sitting on the target — and BFS finds shortest paths in an unweighted graph by exploring it level by level.

Problem, rephrased

You're driving a toy car on an infinite number line. It starts at position 0 with speed +1. You feed it a string of two instructions:

  • 'A' (accelerate): the car moves, then speeds up. position += speed, then speed *= 2.
  • 'R' (reverse): the car flips direction without moving. If speed > 0 it becomes -1; otherwise it becomes +1. position is unchanged.

Given a target position, return the length of the shortest instruction sequence that lands the car exactly on target.

Notice what 'A' does to speed: +1, +2, +4, +8, … — it doubles every time you hold the pedal, so the car covers 1, 3, 7, 15, … (i.e. 2^k - 1) total ground after k straight 'A's. 'R' is your only way to slow down or turn around: it snaps speed back to magnitude 1, pointing the other way.

instruction:   (start)   A      A       A        R          A
position:        0        1      3       7        7          6
speed:          +1       +2     +4      +8       -1         -2
                          ^      ^        ^        ^          ^
                       move+    move+   move+   flip dir   move back
                       speed up        speed up         (now reversing)

Inputs / outputs

target shortest length one optimal sequence what it does
3 2 AA 0→1 (speed 2), 1→3 (speed 4) — lands exactly
6 5 AAARA overshoot to 7, reverse, crawl back one to 6
1 1 A 0→1 in a single accelerate
4 5 AARAR… / AAARRA can't hit 4 with pure As, needs reverses

You return the number of instructions, not the string itself.

Sign in to continue reading

The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.

Sign in to read the full lesson

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.