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

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.