Algorithm Description

A depth-first search is an algorithm wherein a data structure is modeled into a tree and is traversed down toward the leaves of the tree first before continuing to other branches, in search of a target element. A breadth-first search, by comparison, traverses each level of the tree before continuing to the next level. In particular, the siblings of a leaf are traversed before the cousins of a leaf.

Depth-first search should be used when trying to determine if there is any path between two nodes.

Depth-first search can be implemented iteratively using a stack. On each iteration, the top-most (most recently encountered) item is popped off the stack and processed.

The use of a stack vs. a queue is what distinguishes a DFS (stack) from a BFS (queue).


Performance Characteristics

Let $n$ equal the number of nodes in the tree.

In the worst case, the tree might be a linked list, which means the space complexity will be $O(n)$.

Since we may need to visit every node, the runtime complexity of this technique is also $O(n)$.


Puzzles