Условие задачи

Дано двоичное дерево поиска (BST - Binary Search Tree) и два узла в дереве. Необходимо найти наименьшего общего предка (LCA - Lowest Common Ancestor) этих двух узлов в дереве.

Согласно определению LCA на Википедии: "Наименьший общий предок (LCA) двух узлов p и q в дереве T - это узел с наименьшей глубиной, который имеет и p, и q в качестве потомков (где мы разрешаем узлу быть потомком самого себя)."

Примеры

Для двоичного дерева поиска:

        6
       / \\\\
      2   8
     / \\\\ / \\\\
    0  4 7  9
       / \\\\
      3   5

Если мы ищем LCA для узлов 2 и 8, то ответом будет 6.

Если мы ищем LCA для узлов 2 и 4, то ответом будет 2.

Решение

Для того, чтобы решить эту задачу, мы можем использовать следующий алгоритм:

1. Начинаем с корня BST.
2. Если оба узла, p и q, находятся в левом поддереве, переходим к левому поддереву.
3. Если оба узла, p и q, находятся в правом поддереве, переходим к правому поддереву.
4. Если узел находится между p и q (т.е. p < узла < q или q < узла < p), то это наименьший общий предок и мы возвращаем его.
5. Если узел равен одному из узлов, p или q, то этот узел становится текущим LCA.
6. Если один узел находится в левом поддереве, а другой в правом, то текущий узел становится LCA.

Пример решения

Для двоичного дерева поиска:

        6
       / \\\\
      2   8
     / \\\\ / \\\\
    0  4 7  9
       / \\\\
      3   5

Для узлов 2 и 8: