Formally, DFS is an uninformed search that progresses by expanding the first child node of the search tree that appears and thus going deeper and deeper until a goal state is found, or it hits a node that has no children. Then the search backtracks and starts off on the next node.

From an algorithmic point-of view, all freshly expanded nodes are placed at the front of the search queue for expansion.

- DFS is complete - if the tree is finite, then a solution would be found if one exists.
- DFS is optimal with a finite tree and all non-negative path costs.

DFS suffers from non-termination when the length of a path in the search tree is infinite. This can be solved by maintaining an increasing limit on the depth of the tree, which is called iterative deepening depth-first search.

Compare Breadth-first search.