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.
💡 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
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
- 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.
Binary Tree Right Side View
Core idea: Stand to the right of the tree and squint. From each horizontal level, exactly one node survives the squint — the one furthest right that nothing else hides. So the answer is just the last node of every level, top to bottom. A level-order BFS hands you each level as a tidy list; grab its last element and you're done.
1. The problem, in a fresh setting
You're building an org-chart viewer. Employees form a tree: the CEO at the root, each manager's reports as children. The product team wants a "skyline" widget — when the whole org is collapsed to one node per management layer, they want the rightmost-positioned person at each depth (the convention is: the last report listed under each manager wins the tie within that layer). Reading top to bottom, that list is the silhouette you'd see looking at the chart from the right edge.
Formally: given the root of a binary tree, return the values of the nodes you can see from the right side, ordered top to bottom. "Visible from the right" means: for each depth, the node that appears last when you read that level left-to-right — because every node to its left is hidden behind it from the right-hand viewpoint.
Here's a small tree:
| Level | Nodes (left → right) | Rightmost (visible) |
|---|---|---|
| 0 | 1 |
1 |
| 1 | 2, 3 |
3 |
| 2 | 5, 4 |
4 |
Expected output: [1, 3, 4].
Note the subtlety already: at level 1 the visible node is 3 (a right child), but the visible node could just as easily have been a left child if 3 had no right subtree. "Rightmost on the level" is not the same as "follow right pointers" — more on that in a moment.
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