Как определить наименьший общий предок в бинарном дереве

Что проверяют

Умеете ли вы решить задачу рекурсией и объяснить, почему решение работает, а не просто вспомнить код. Уточнения идут почти всегда: а если это BST, а если одного узла нет в дереве, а если запросов миллион.

Как отвечать

Начните с условий: обычное бинарное дерево или дерево поиска, гарантировано ли, что оба узла есть, хранится ли ссылка на родителя.

Базовое решение для обычного дерева, обход в глубину:

• если текущий узел null или совпал с p или q, вернуть его;
• рекурсивно спросить левое и правое поддерево;
• оба вернули не null: узлы разошлись по разным сторонам, текущий узел и есть ответ;
• иначе поднять наверх тот результат, что не null.

Сложность O(n) по времени и O(h) по стеку, где h высота дерева: O(log n) для сбалансированного, O(n) для вырожденного.

Варианты, которые стоит назвать:

• BST: идём влево, если оба значения меньше текущего, вправо, если оба больше, иначе текущий узел и есть ответ. O(h), пишется циклом без стека;
• ссылка на родителя: поднимаемся от p к корню, складываем предков в HashSet, затем идём вверх от q до первого совпадения. Или как пересечение двух списков, с O(1) памяти;
• много запросов: двоичный подъём (binary lifting) с предобработкой O(n log n) и ответом за O(log n), либо эйлеров обход плюс RMQ;
• узла может не быть: классический код вернёт p, даже если q в дереве нет. Нужно считать найденные узлы и отдавать ответ, только если нашлись оба.

Где спотыкаются

Применяют логику BST к обычному дереву. Сравнение значений работает только при упорядоченности, на произвольном дереве ответ получается неверным.

Сравнивают узлы по val, а не по ссылке через ==. При повторяющихся значениях алгоритм найдёт не тот узел.

Не думают о глубине. На вырожденном дереве в сотни тысяч узлов рекурсия в Java упирается в StackOverflowError, и интервьюер ждёт итеративный вариант: Deque для обхода и HashMap с родителями.