Depth-first search (DFS) is a method for exploring a tree or graph. In a DFS, you go as deep as possible down one path before backing up and trying a different one.

Depth-first search is like walking through a corn maze. You explore one path, hit a dead end, and go back and try a different one.

It employs the following rules.

  • Rule 1 − Visit the adjacent unvisited Mark it as visited. Display it. Push it in a stack.
  • Rule 2 − If no adjacent vertex is found, pop up a vertex from the stack. (It will pop up all the vertices from the stack, which do not have adjacent vertices.)
  • Rule 3 − Repeat Rule 1 and Rule 2 until the stack is empty.

Here's a how a DFS would traverse this tree, starting with the root:

                                               

We'd go down the first path we find until we hit a dead end:

                                               

Then we'd do the same thing again go down a path until we hit a dead end:

                                                 

And again:

                                                 

And again:

                                                   

Until we reach the end.

Depth-first search is often compared with breadth-first search.

Advantages:

  • Depth-first search on a binary tree generally requires less memory than breadth-first.
  • Depth-first search can be easily implemented with recursion.

Disadvantages:

  •  A DFS doesn't necessarily find the shortest path to a node, while breadth-first search does.