Двоичное дерево здесь не обязательно может быть двоичным деревом поиска.
Структура может быть принята как -

struct node {
    int data;
    struct node *left;
    struct node *right;
};

Максимальное решение, которое я мог решить с другом, было что-то в этом роде -
Рассмотреть возможностьэто двоичное дерево :

Двоичное дерево http://lcm.csa.iisc.ernet.in/dsa/img151.gif

Выход по обходу по порядку - 8, 4, 9, 2, 5, 1, 6, 3, 7

А доходность прохождения заказа - 8, 9, 4, 5, 2, 6, 7, 3, 1

Так, например, если мы хотим найти общего предка узлов 8 и 5, то мы составляем список всех узлов, которые находятся между 8 и 5 в обходе дерева порядков, которое в этом случае оказывается [4, 9 , 2]. Затем мы проверяем, какой узел в этом списке появляется последним в прохождении после заказа, а это 2. Следовательно, общий предок для 8 и 5 равен 2.

Я полагаю, что сложность этого алгоритма состоит в O (n) (O (n) для обходов по порядку / порядку, остальные шаги снова являются O (n), поскольку они являются не более чем простыми итерациями в массивах). Но есть большая вероятность, что это неправильно. :-)

Но это очень грубый подход, и я не уверен, что он сломается в каком-то случае. Есть ли другое (возможно, более оптимальное) решение этой проблемы?