DFS

Abstract

---

Use Cases

• When you only care about whether a path exists
• When the graph might be cyclic (just need proper visited[] handling)
• When you want a simple recursive implementation

Complexity Analysis

• Time Complexity: $O(V+E)$ (visit each node and edge once)
• Space Complexity: $O(V)$ for visited and recursion stack

Pros

• Easy to write recursively
• Works fine for reachability
• Low memory footprint

Cons

• Might explore long wrong paths first
• Not guaranteed to find the shortest path

Practice Questions

206. Reverse Linked List

19. Remove Nth Node From End of List

DFS with Backtracking

---

Use Cases

• When you need to explore all possible paths/solutions
• When you must undo decisions to try other paths (e.g., unmark visited)
• Classic in combinatorial search, puzzles, and path enumeration

Complexity Analysis

• Time Complexity: Worst-case $O(2^n)$ (explores all paths)

Pros

• Finds all paths, all solutions, all combinations
• Works for grid problems, games, puzzle solving

Cons

• Overkill for reachability
• Can be very slow and even TLE if graph has cycles and large branching
• Must be careful with revisiting nodes