При поиске в глубину всегда развертывается самый глубокий узел в текущей периферии дерева поиска. Ход такого поиска показан на рис. 3.8. Поиск непосредственно переходит на самый глубокий уровень дерева поиска, на котором узлы не имеют преемников. По мере того как эти узлы развертываются, они удаляются из периферии, поэтому в дальнейшем поиск "возобновляется" со следующего самого поверхностного узла, который все еще имеет неисследованных преемников.

Рис. 3.8. Поиск в глубину в бинарном дереве. Узлы, которые были развернуты и не имеют потомков в этой периферии, могут быть удалены из памяти; эти узлы обозначены черным цветом. Предполагается, что узлы на глубине 3 не имеют преемников и единственным целевым узлом является М

Эта стратегия может быть реализована в процедуре Tree-Search с помощью очереди LIFO (Last-In-First-Out), называемой также стеком. В качестве альтернативы способу реализации на основе процедуры Tree-Search поиск в глубину часто реализуют с помощью рекурсивной функции, вызывающей саму себя в каждом из дочерних узлов по очереди. (Рекурсивный алгоритм поиска в глубину, в котором предусмотрен предел глубины, приведен в листинге 3.4.)

Поиск в глубину имеет очень скромные потребности в памяти. Он требует хранения только единственного пути от корня до листового узла, наряду с оставшимися неразвернутыми сестринскими узлами для каждого узла пути. После того как был развернут некоторый узел, он может быть удален из памяти, коль скоро будут полностью исследованы все его потомки (см. рис. 3.8). Для пространства состояний с коэффициентом ветвления Ь и максимальной глубиной т поиск в глубину требует хранения только bт+1 узлов. Используя такие же предположения, как и в табл. 3.1, и допуская, что узлы, находящиеся на той же глубине, что и целевой узел, не имеют преемников, авторы определили, что на глубине d=12 для поиска в глубину требуется 118 килобайтов вместо 10 петабайтов, т.е. потребность в пространстве уменьшается примерно в 10 миллиардов раз.