El árbol binario aquí puede no ser necesariamente un árbol binario de búsqueda.
La estructura podría ser tomada como

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

La solución máxima que pude encontrar con un amigo era algo de este tipo:
Considerareste árbol binario :

Árbol binario http://lcm.csa.iisc.ernet.in/dsa/img151.gif

Los rendimientos de recorrido de orden - 8, 4, 9, 2, 5, 1, 6, 3, 7

Y los rendimientos transversales posteriores al pedido - 8, 9, 4, 5, 2, 6, 7, 3, 1

Entonces, por ejemplo, si queremos encontrar el ancestro común de los nodos 8 y 5, entonces hacemos una lista de todos los nodos que están entre 8 y 5 en el recorrido transversal del árbol inorder, que en este caso es [4, 9 , 2]. Luego verificamos qué nodo de esta lista aparece en último lugar en el recorrido del orden posterior, que es 2. Por lo tanto, el ancestro común para 8 y 5 es 2.

La complejidad de este algoritmo, creo que es O (n) (O (n) para los recorridos inorder / postorder, el resto de los pasos nuevamente son O (n), ya que no son más que simples iteraciones en arreglos). Pero hay una gran posibilidad de que esto esté mal. :-)

Pero este es un enfoque muy crudo, y no estoy seguro si se descompone en algún caso. ¿Hay alguna otra solución (posiblemente más óptima) para este problema?