Trees & GraphsMedium

DFS

Go as deep as possible before backtracking using a stack or recursion.

How it works

Depth-First Search explores as far as possible along a branch before backtracking. It can be implemented recursively (using the call stack implicitly) or iteratively (using an explicit stack). DFS is ideal when you need to explore all paths, detect cycles, or determine reachability. In trees, DFS naturally produces preorder, inorder, and postorder traversals depending on when you process the current node relative to its children. For graphs, maintain a visited set to prevent infinite loops. DFS is also the backbone of topological sort (process nodes in reverse finish order) and strongly connected components (Tarjan's / Kosaraju's algorithm).

Interactive Playground

Start at node 1. Push to call stack. Mark visited.

Speed

When to use

Cycle detection and topological sort
Connected components and flood fill
Exploring all paths in a graph

✅Tips

1Recursive DFS is cleaner; iterative DFS with an explicit stack is needed when recursion depth exceeds limits.

2For cycle detection in directed graphs, use three states: unvisited (0), in-stack (1), done (2).

3Postorder DFS (process node after children) is useful for bottom-up computations like tree height or subtree sums.

4For flood fill / connected components, DFS with in-place modification (mark visited by changing the value) saves space.

❌Common Mistakes

!Forgetting the visited set in graph DFS — causes infinite loops in cyclic graphs.

!Confusing tree DFS (no visited set needed, no cycles) with graph DFS (needs visited set).

!Using preorder when postorder is needed — e.g., returning subtree info before children are processed.

!Stack overflow on very deep recursion (e.g., a chain of 10^5 nodes) — convert to iterative.

💡 Key Insight:DFS order determines preorder / inorder / postorder traversal of trees.

Solved Problems0

No solved problems yet.

Related Patterns

BFS→Tree Traversal→