Depth-First Search — Graph & Tree Traversal

What Is DFS?

Depth-First Search (DFS) explores a graph or tree by going as deep as possible down one path before backtracking and trying another.

Think of navigating a maze: you pick a corridor and walk until you hit a dead end, then backtrack to the last junction and try a different turn.

How It Works

Starting from a source node:

1. Mark the current node as visited
2. Explore each unvisited neighbour recursively (or via a stack)
3. When all neighbours are visited, backtrack

Implementation

• Time Complexity: O(V + E) — visits every vertex and edge once
• Space Complexity: O(V) — recursion stack depth (or explicit stack)

Interactive Lab

Watch DFS push neighbours onto the call stack and backtrack when a dead end is reached.

DFS on Trees

On a binary tree, DFS naturally produces three orderings based on when you process the root:

Key Applications

• Cycle detection in directed/undirected graphs
• Topological sort (dependency ordering)
• Path finding between two nodes
• Connected components — count isolated regions
• Solving puzzles (mazes, Sudoku) via backtracking

DFS vs BFS — When to Use Which

Key Takeaway

DFS is your go-to when you need to explore all reachable states. Its recursive nature maps cleanly onto tree/graph structures. Watch out for cycles in graphs — always track visited nodes.