Coding Interview Prep · 70 min · Python

Trees & Graphs: DFS, BFS & Backtracking

DFS explores; BFS levels. Know which you need before you write a single line.

Hiring signal: Traverses any tree or graph confidently, choosing DFS vs BFS by the problem shape

What you will learn

Implement recursive and iterative DFS for binary trees and graphs
Implement BFS with a queue for level-order and shortest-path problems
Choose DFS vs BFS by matching the problem's structure
Apply backtracking to generate combinations and permutations
Implement topological sort (Kahn's algorithm) for dependency ordering

The Problem

Tree and graph problems make up a huge slice of the ML interview screen. DAGs appear in ML pipelines, computation graphs, and dependency resolution. Trees appear in decision-tree proofs, hierarchical data, and virtually every "design a system" whiteboard. The patterns are small but must be automatic — you should write a BFS or DFS without thinking, so your mental CPU is free for the actual problem.

The Concept

DFS vs BFS: The Fundamental Choice

Every tree/graph problem starts with one decision: depth-first or breadth-first? The choice is not about preference — it's about what you're looking for:

DFS (depth-first search) goes deep before going wide. It explores one path all the way to a leaf before backtracking. Use DFS when you need to: find any path (not necessarily shortest), examine the full structure of a subtree, enumerate all possible solutions (with backtracking), or compute something over a path (max depth, path sum). DFS uses a stack (or recursion, which is an implicit stack) and uses O(h) space where h is the height.

BFS (breadth-first search) goes wide before going deep. It explores all nodes at distance 1, then distance 2, then distance 3. Use BFS when you need to: find the shortest path in an unweighted graph (BFS guarantees the first time you reach a node is via the shortest path), process nodes level by level, or find the nearest node satisfying a condition. BFS uses a queue and uses O(w) space where w is the maximum width of the tree.

The critical insight: BFS finds shortest paths; DFS finds paths. If the problem says "shortest," "nearest," "minimum steps," or "fewest edges" in an unweighted graph — BFS. If the problem says "all paths," "does a path exist," "maximum depth," or involves backtracking — DFS.

Unlock the full lesson

You've read the first 2 sections. The rest of this lesson covers The Patterns, Interview Discipline, Ship It, Use It, Evaluation, Exercises, Key Terms, Common Pitfalls, Interview Framing — plus a hands-on lab, quiz, and project artifact.

Create a free account to unlock Phase 0 and Phase 1 of every course — no credit card.