Определение:

Поиск в глубину — это алгоритм, ищущий по дереву (или графу) сначала в глубину начиная с корня.

Алгоритм идёт по дереву, переходя между уровнями по левым дочерним узлам, пока не дойдёт до самого низа.
Завершив проход по ветви, алгоритм возвращается обратно, просматривая правые дочерние узлы этой ветви. Причём, если возможно, выбирает самые левые из узлов, расположенных справа от предыдущего маршрута.
Завершив просмотр всей ветви, алгоритм переходит к узлу, расположенному справа от корня, и снова идёт по левым дочерним узлам до самого дна.
Последним анализируется крайний правый узел (расположенный справа от всех своих предшественников).

Что вам нужно знать:

Алгоритм оптимален для поиска по дереву, чья глубина превышает ширину.
Для работы алгоритма используется стек.
Поскольку стек является LIFO-структурой, ему не нужно отслеживать указатели узлов, поэтому потребляется меньше памяти, чем в случае с поиском в ширину.
Когда алгоритм не может дальше идти по левой стороне, он начинает анализировать стек.

Эффективность («О» большое):