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

Remove Invalid Parentheses

Core idea: You're handed a string of parentheses (and maybe other letters) that's almost valid, and you must delete the fewest characters to fix it — then list every distinct repaired string achievable with that minimum number of deletions. The trick is to stop thinking "which brackets are wrong?" and start thinking "how few deletions to reach a valid state?" Picture each string as a node, and draw an edge from a string to every string you get by removing exactly one character — that's an implicit state graph, and "fewest deletions to validity" is just the shortest path to any valid node. Every deletion costs the same one step, so the right tool is BFS: it fans out in levels of equal removal-count, and the first level that contains any valid string holds all the minimum-removal answers.

1. The problem, in a fresh setting

You maintain a config repair tool. A user submits a bracketed expression — say a filter like ()())() — and it doesn't parse: there are stray brackets. Your tool must propose repairs, but with two rules: (1) delete as few characters as possible (don't mangle the user's intent more than necessary), and (2) since there can be several equally-minimal repairs, show the user all of them so they can pick. You never want to show a repair that deleted more than the bare minimum.

Formally: given a string s containing (, ), and possibly other characters, remove the minimum number of invalid parentheses to make s valid, and return all distinct valid strings achievable with that minimum removal count. A string is valid when every ) has a matching earlier ( and no ( is left unclosed; non-parenthesis characters are always fine and may not be removed for validity's sake (but the algorithm is free to consider removing brackets only).

s Output (any order) Min removals Note
"()())()" ["(())()", "()()()"] 1 two distinct one-deletion repairs
"(a)())()" ["(a())()", "(a)()()"] 1 letters left untouched
")(" [""] 2 both brackets are stray
"(((") [""] (shown as [""]) 3 all three are unmatched openers
"" [""] 0 already valid

The output list is a set of distinct strings; order doesn't matter.

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.