DFS Visualization: Depth-First Search Simulator

Q: What is the time complexity of DFS?

O(b^m) time and O(b·m) space in a tree, where m is the maximum depth; O(V + E) on a graph with an explored set.

About this visualization

Depth-first search follows one branch as deep as it can and backs up only when it reaches a dead end, using a last-in-first-out stack. It needs little memory but can return long, expensive paths. Build a graph and watch the stack grow and shrink.

How it works

Put the start node on a stack.
Pop the top node; if it is the goal, stop. Otherwise push its unexplored neighbours.
The most recently found node is always explored next, so the search plunges down one branch before trying another.

Formulas used

Time: $O(b^{m})$ Space: $O(b\cdot m)$
$m$ = maximum depth of the search space

Worked example

On the 15-node binary tree with goal K, DFS expands A, B, D, H, I, E, J and then reaches K, visiting the left side first. BFS would have expanded A through J level by level. Both find A → B → E → K here, but DFS took a very different route to get there.

Enter these numbers in the simulator above to see every step.

Complexity and properties

Worst case	$O(b^{m})$
Space	$O(b\cdot m)$

Not optimal. Not complete in infinite or cyclic spaces unless it remembers explored nodes (as here).

When to use it

Finding any path or checking connectivity.
Topological sorting, cycle detection and maze solving.
Understanding memory-light search.

Frequently asked questions

What is the time complexity of DFS?

$O(b^{m})$ time and $O(b\cdot m)$ space in a tree, where m is the maximum depth; $O(V + E)$ on a graph with an explored set.

Is DFS complete and optimal?

It is not optimal, and it is incomplete in infinite or cyclic spaces unless it remembers explored nodes.

What data structure does DFS use?

A stack — explicitly, or implicitly through recursion.