¿Cómo encontrar el ancestro común más bajo de dos nodos en cualquier árbol binario?

El Árbol Binario aquí puede no ser necesariamente un Árbol de Búsqueda Binario.
La estructura podría tomarse 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 -
Considere este árbol binario :

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

El recorrido del orden rinde - 8, 4, 9, 2, 5, 1, 6, 3, 7

Y los rendimientos de recorrido postorden- 8, 9, 4, 5, 2, 6, 7, 3, 1

Así que para 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 del árbol de orden, que en este caso pasa a ser [4, 9, 2]. Luego comprobamos qué nodo de esta lista aparece el último en el recorrido postorder, que es 2. Por lo tanto, el ancestro común para 8 y 5 es 2.

La complejidad para este algoritmo, creo que es O (n) (O (n) para traversals inorder / postorder, el resto de los pasos nuevamente siendo O (n) ya que son nada más que simples iteraciones en arrays). Pero hay muchas posibilidades de que esto esté mal. :-)

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