Coding

DFS

A fundamental graph traversal algorithm that explores as far as possible along each branch before backtracking, utilizing a Last-In-First-Out (LIFO) approach.

Cheat Sheet

Prime Use Case

Use DFS when you need to explore all nodes/paths, detect cycles, perform topological sorts, or solve puzzles where you must reach a leaf node before making a new decision.

Critical Tradeoffs

  • Time Complexity: O(V + E) where V is vertices and E is edges
  • Space Complexity: O(H) where H is the maximum height/depth of the tree/graph
  • Memory efficient for wide trees compared to BFS
  • Does not guarantee the shortest path in unweighted graphs

Killer Senior Insight

DFS is the engine of Backtracking; it treats the state-space as a tree where each recursive call is a decision, and returning from the call is 'undoing' that decision.

Recognition

Common Interview Phrases

Find all possible paths from A to B
Check if a cycle exists in the graph
Find the topological ordering of tasks
Explore all connected components in a grid
Solve a constraint satisfaction problem (e.g., Sudoku)

Common Scenarios

  • Tree traversals (Pre-order, In-order, Post-order)
  • Finding strongly connected components (Tarjan's or Kosaraju's)
  • Flood fill algorithms in image processing or grid games
  • Pathfinding in mazes where any path is acceptable

Anti-patterns to Avoid

  • Using DFS for shortest path in an unweighted graph (BFS is the standard)
  • Applying recursive DFS to graphs with millions of nodes without increasing stack size
  • Using DFS on infinite graphs without a depth limit (Iterative Deepening is preferred)

The Problem

The Fundamental Issue

Systematically visiting every reachable node in a graph structure without redundant processing or getting trapped in infinite loops.

What breaks without it

Stack Overflow or Infinite Loops in cyclic graphs

Incomplete exploration of the search space

Inefficient memory usage (MLE) when trying to store all possible paths simultaneously

Why alternatives fail

BFS requires O(W) space (Width), which is catastrophic for very wide trees (e.g., a tree with a branching factor of 10 and depth of 5).

Simple iteration cannot easily track the 'path' taken to reach a specific node without complex auxiliary structures.

Mental Model

The Intuition

Imagine exploring a dark maze with a ball of string and a piece of chalk. You follow one path until you hit a dead end or a chalk mark (visited node), then you reel the string back to the last junction to try a different path.

Key Mechanics

1

Recursive Function Call (Implicit Stack) or Explicit Stack object

2

Visited Set/Array to track explored nodes and prevent cycles

3

Base Case to terminate recursion (e.g., target found or leaf reached)

4

Backtracking step where state is reset after a recursive call returns

Framework

When it's the best choice

  • The solution is likely far from the root (deep in the tree)
  • Memory is a constraint and the graph is very wide
  • You need to perform an exhaustive search of all permutations/combinations

When to avoid

  • The graph is extremely deep or infinite
  • You need the absolute shortest path in an unweighted graph
  • The target node is likely close to the starting point

Fast Heuristics

If N is small and you need all paths: DFS with Backtracking
If you need the shortest path: BFS
If the tree is deep and wide: Iterative Deepening DFS

Tradeoffs

+

Strengths

  • Low memory footprint for deep, narrow trees (O(H))
  • Easier to implement recursively for complex state-space searches
  • Naturally supports post-order processing (useful for dependency resolution)
−

Weaknesses

  • Can get 'lost' in a deep branch that doesn't contain the solution
  • Risk of StackOverflowError in environments with limited recursion depth
  • Not optimal for finding the nearest neighbor

Alternatives

BFS
Alternative

When it wins

Finding the shortest path in unweighted graphs or searching nodes close to the source.

Key Difference

Uses a Queue (FIFO) to explore level-by-level rather than branch-by-branch.

Iterative Deepening DFS
Alternative

When it wins

When you want the shortest path guarantee of BFS but the space efficiency of DFS.

Key Difference

Performs repeated DFS with increasing depth limits.

Dijkstra's Algorithm
Alternative

When it wins

Finding the shortest path in a weighted graph.

Key Difference

Uses a Priority Queue to explore nodes based on cumulative edge weights.

Execution

Must-hit talking points

  • Explicitly mention the O(H) space complexity and why it matters for memory-constrained systems.
  • Discuss the difference between Pre-order and Post-order processing in the context of the problem.
  • Explain how to handle cycles using a 'visited' set or 'three-color' marking (White/Gray/Black).
  • Mention the possibility of converting the recursive solution to an iterative one using an explicit stack to avoid stack overflow.

Anticipate follow-ups

  • Q:"How would you modify this to detect a cycle in a directed vs undirected graph?"
  • Q:"What happens if the graph is too large to fit in memory? (External DFS)"
  • Q:"Can you implement this without recursion?"
  • Q:"How does DFS help in finding the diameter of a tree?"

Red Flags

Forgetting to mark a node as visited before the recursive call.

Why it fails: Causes infinite recursion in graphs with cycles, leading to a StackOverflowError.

Not resetting the 'visited' state during backtracking when searching for ALL paths.

Why it fails: The algorithm will skip valid paths because it thinks a node was already 'used' in a different branch.

Assuming DFS finds the shortest path.

Why it fails: DFS explores one branch fully; it might find a path of length 100 before finding a path of length 2 that was in a different branch.