¿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 binaria.
La estructura podría tomarse como:

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

La solución máxima que pude resolver con un amigo fue algo así:
considere este árbol binario :

El rendimiento transversal del pedido: 8, 4, 9, 2, 5, 1, 6, 3, 7

Y los rendimientos transversales del postorder - 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 del árbol de pedidos, que en este caso es [4, 9 2]. Luego verificamos qué nodo en esta lista aparece último en el recorrido del postorder, 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 recorridos de orden / postorder, el resto de los pasos nuevamente son O (n) ya que no son más que simples iteraciones en matrices). Pero existe una gran posibilidad de que esto esté mal. :-)

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

Nick Johnson tiene razón en que un algoritmo de complejidad de tiempo O (n) es lo mejor que puede hacer si no tiene punteros principales.) Para una versión recursiva simple de ese algoritmo, vea el código en la publicación de Kinding que se ejecuta en tiempo O (n) .

Pero tenga en cuenta que si sus nodos tienen punteros principales, es posible un algoritmo mejorado. Para ambos nodos en cuestión, construya una lista que contenga la ruta desde la raíz hasta el nodo comenzando en el nodo e insertando el padre por delante.

Entonces, para 8 en su ejemplo, obtiene (mostrando pasos): {4}, {2, 4}, {1, 2, 4}

Haga lo mismo para su otro nodo en cuestión, resultando en (pasos no mostrados): {1, 2}

Ahora compare las dos listas que hizo buscando el primer elemento donde la lista difiere, o el último elemento de una de las listas, lo que ocurra primero.

Este algoritmo requiere un tiempo O (h) donde h es la altura del árbol. En el peor de los casos, O (h) es equivalente a O (n), pero si el árbol está equilibrado, eso es solo O (log (n)). También requiere espacio O (h). Es posible una versión mejorada que use solo espacio constante, con el código mostrado en la publicación de CEGRD

Independientemente de cómo se construya el árbol, si esta será una operación que realizará muchas veces en el árbol sin cambiarla, hay otros algoritmos que puede usar que requieren una preparación de tiempo O (n) [lineal], pero luego encontrar cualquier el par solo toma O (1) [constante] tiempo. Para obtener referencias a estos algoritmos, consulte la página con el problema de antepasado común más bajo en Wikipedia . (Crédito a Jason por publicar originalmente este enlace)

Comenzando desde el rootnodo y moviéndose hacia abajo si encuentra algún nodo que tenga uno po qcomo su hijo directo, entonces es el LCA. (edit - esto debería ser si po qes el valor del nodo, devuélvalo De lo contrario, se producirá un error cuando uno de. po qes un hijo directo de la otra.)

De lo contrario, si encuentra un nodo con psu subárbol derecho (o izquierdo) y qsu subárbol izquierdo (o derecho), entonces es el LCA.

El código fijo se ve así:

treeNodePtr findLCA(treeNodePtr root, treeNodePtr p, treeNodePtr q) {

        // no root no LCA.
        if(!root) {
                return NULL;
        }

        // if either p or q is the root then root is LCA.
        if(root==p || root==q) {
                return root;
        } else {
                // get LCA of p and q in left subtree.
                treeNodePtr l=findLCA(root->left , p , q);

                // get LCA of p and q in right subtree.
                treeNodePtr r=findLCA(root->right , p, q);

                // if one of p or q is in leftsubtree and other is in right
                // then root it the LCA.
                if(l && r) {
                        return root;
                }
                // else if l is not null, l is LCA.
                else if(l) {
                        return l;
                } else {
                        return r;
                }
        }
}

El siguiente código falla cuando cualquiera es hijo directo de otro.

treeNodePtr findLCA(treeNodePtr root, treeNodePtr p, treeNodePtr q) {

        // no root no LCA.
        if(!root) {
                return NULL;
        }

        // if either p or q is direct child of root then root is LCA.
        if(root->left==p || root->left==q || 
           root->right ==p || root->right ==q) {
                return root;
        } else {
                // get LCA of p and q in left subtree.
                treeNodePtr l=findLCA(root->left , p , q);

                // get LCA of p and q in right subtree.
                treeNodePtr r=findLCA(root->right , p, q);

                // if one of p or q is in leftsubtree and other is in right
                // then root it the LCA.
                if(l && r) {
                        return root;
                }
                // else if l is not null, l is LCA.
                else if(l) {
                        return l;
                } else {
                        return r;
                }
        }
}

Código en acción

Aquí está el código de trabajo en JAVA

public static Node LCA(Node root, Node a, Node b) {
   if (root == null) {
       return null;
   }

   // If the root is one of a or b, then it is the LCA
   if (root == a || root == b) {
       return root;
   }

   Node left = LCA(root.left, a, b);
   Node right = LCA(root.right, a, b);

   // If both nodes lie in left or right then their LCA is in left or right,
   // Otherwise root is their LCA
   if (left != null && right != null) {
      return root;
   }

   return (left != null) ? left : right; 
}

Las respuestas dadas hasta ahora usan recursividad o almacena, por ejemplo, una ruta en la memoria.

Ambos enfoques pueden fallar si tiene un árbol muy profundo.

Aquí está mi opinión sobre esta pregunta. Cuando verificamos la profundidad (distancia desde la raíz) de ambos nodos, si son iguales, entonces podemos movernos con seguridad hacia arriba desde ambos nodos hacia el ancestro común. Si una de las profundidades es más grande, entonces debemos movernos hacia arriba desde el nodo más profundo mientras permanecemos en el otro.

Aquí está el código:

findLowestCommonAncestor(v,w):
  depth_vv = depth(v);
  depth_ww = depth(w);

  vv = v; 
  ww = w;

  while( depth_vv != depth_ww ) {
    if ( depth_vv > depth_ww ) {
      vv = parent(vv);
      depth_vv--;
    else {
      ww = parent(ww);
      depth_ww--;
    }
  }

  while( vv != ww ) {
    vv = parent(vv);
    ww = parent(ww);
  }

  return vv;    

La complejidad temporal de este algoritmo es: O (n). La complejidad espacial de este algoritmo es: O (1).

Con respecto al cálculo de la profundidad, primero podemos recordar la definición: Si v es raíz, profundidad (v) = 0; De lo contrario, profundidad (v) = profundidad (padre (v)) + 1. Podemos calcular la profundidad de la siguiente manera:

depth(v):
  int d = 0;
  vv = v;
  while ( vv is not root ) {
    vv = parent(vv);
    d++;
  }
  return d;

Bueno, este tipo de depende de cómo está estructurado su árbol binario. Presumiblemente, tiene alguna forma de encontrar el nodo de hoja deseado dada la raíz del árbol: simplemente aplique eso a ambos valores hasta que las ramas que elija diverjan.

Si no tiene una manera de encontrar la hoja deseada dada la raíz, entonces su única solución, tanto en operación normal como para encontrar el último nodo común, es una búsqueda de fuerza bruta del árbol.

Esto se puede encontrar en: - http://goursaha.freeoda.com/DataStructure/LowestCommonAncestor.html

 tree_node_type *LowestCommonAncestor(
 tree_node_type *root , tree_node_type *p , tree_node_type *q)
 {
     tree_node_type *l , *r , *temp;
     if(root==NULL)
     {
        return NULL;
     }

    if(root->left==p || root->left==q || root->right ==p || root->right ==q)
    {
        return root;
    }
    else
    {
        l=LowestCommonAncestor(root->left , p , q);
        r=LowestCommonAncestor(root->right , p, q);

        if(l!=NULL && r!=NULL)
        {
            return root;
        }
        else
        {
        temp = (l!=NULL)?l:r;
        return temp;
        }
    }
}

El algoritmo de antepasados ​​menos comunes fuera de línea de Tarjan es lo suficientemente bueno (véase también Wikipedia ). Hay más información sobre el problema (el problema ancestral más bajo) en Wikipedia .

Para descubrir el ancestro común de dos nodos: -

• Encuentre el nodo dado Nodo1 en el árbol utilizando la búsqueda binaria y guarde todos los nodos visitados en este proceso en una matriz, digamos A1. Tiempo - O (logn), Espacio - O (logn)
• Encuentre el Nodo2 dado en el árbol utilizando la búsqueda binaria y guarde todos los nodos visitados en este proceso en una matriz, digamos A2. Tiempo - O (logn), Espacio - O (logn)
• Si la lista A1 o la lista A2 está vacía, entonces el nodo no existe, por lo que no hay un ancestro común.
• Si la lista A1 y la lista A2 no están vacías, busque en la lista hasta que encuentre un nodo que no coincida. Tan pronto como encuentre dicho nodo, el nodo anterior es un ancestro común.

Esto funcionaría para el árbol de búsqueda binario.

Intenté con imágenes ilustrativas y código de trabajo en Java,

http://tech.bragboy.com/2010/02/least-common-ancestor-without-using.html

El siguiente algoritmo recursivo se ejecutará en O (log N) para un árbol binario equilibrado. Si cualquiera de los nodos pasados ​​a la función getLCA () es el mismo que la raíz, entonces la raíz será el LCA y no habrá necesidad de realizar ninguna recusación.

Casos de prueba. [1] Ambos nodos n1 y n2 están en el árbol y residen a ambos lados de su nodo padre. [2] O bien el nodo n1 o n2 es la raíz, el LCA es la raíz. [3] Solo n1 o n2 están en el árbol, LCA será el nodo raíz del subárbol izquierdo de la raíz del árbol, o LCA será el nodo raíz del subárbol derecho de la raíz del árbol.

[4] Ni n1 ni n2 están en el árbol, no hay LCA. [5] Tanto n1 como n2 están en línea recta uno al lado del otro, LCA será de n1 o n2 que alguna vez esté cerca de la raíz del árbol.

//find the search node below root
bool findNode(node* root, node* search)
{
    //base case
    if(root == NULL)
        return false;

    if(root->val == search->val)
        return true;

    //search for the node in the left and right subtrees, if found in either return true
    return (findNode(root->left, search) || findNode(root->right, search));
}

//returns the LCA, n1 & n2 are the 2 nodes for which we are
//establishing the LCA for
node* getLCA(node* root, node* n1, node* n2)
{
    //base case
    if(root == NULL)
        return NULL;

    //If 1 of the nodes is the root then the root is the LCA
    //no need to recurse.
    if(n1 == root || n2 == root)
        return root;

    //check on which side of the root n1 and n2 reside
    bool n1OnLeft = findNode(root->left, n1);
    bool n2OnLeft = findNode(root->left, n2);

    //n1 & n2 are on different sides of the root, so root is the LCA
    if(n1OnLeft != n2OnLeft)
        return root;

    //if both n1 & n2 are on the left of the root traverse left sub tree only
    //to find the node where n1 & n2 diverge otherwise traverse right subtree
    if(n1OnLeft)
        return getLCA(root->left, n1, n2);
    else
        return getLCA(root->right, n1, n2);
}

Simplemente baje de todo el árbol rootsiempre que ambos nodos dados, digamos pyq , para los cuales se debe encontrar Ancestor, se encuentren en el mismo subárbol (lo que significa que sus valores son más pequeños o más grandes que los de la raíz).

Esto camina directamente desde la raíz hasta el Ancestro Menos Común, sin mirar el resto del árbol, por lo que es casi tan rápido como puede. Algunas formas de hacerlo.

Iterativo, O (1) espacio

Pitón

def lowestCommonAncestor(self, root, p, q):
    while (root.val - p.val) * (root.val - q.val) > 0:
        root = (root.left, root.right)[p.val > root.val]
    return root

Java

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    while ((root.val - p.val) * (root.val - q.val) > 0)
        root = p.val < root.val ? root.left : root.right;
    return root;
}

en caso de desbordamiento, haría (root.val - (long) p.val) * (root.val - (long) q.val)

Recursivo

Pitón

def lowestCommonAncestor(self, root, p, q):
    next = p.val < root.val > q.val and root.left or \
           p.val > root.val < q.val and root.right
    return self.lowestCommonAncestor(next, p, q) if next else root

Java

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    return (root.val - p.val) * (root.val - q.val) < 1 ? root :
           lowestCommonAncestor(p.val < root.val ? root.left : root.right, p, q);
}

Node *LCA(Node *root, Node *p, Node *q) {
  if (!root) return NULL;
  if (root == p || root == q) return root;
  Node *L = LCA(root->left, p, q);
  Node *R = LCA(root->right, p, q);
  if (L && R) return root;  // if p and q are on both sides
  return L ? L : R;  // either one of p,q is on one side OR p,q is not in L&R subtrees
}

Considera este árbol

Si hacemos un recorrido de postorder y preorder y encontramos el primer predecesor y sucesor común que ocurre, obtenemos el ancestro común.

postorder => 0,2,1,5,4,6,3,8,10,11,9,14,15,13,12,7 preorder => 7,3,1,0,2,6,4 , 5,12,9,8,11,10,13,15,14

• por ejemplo: 1

Antepasado mínimo común de 8,11

en postorder tenemos => 9,14,15,13,12,7 después de 8 y 11 en preorden tenemos => 7,3,1,0,2,6,4,5,12,9 antes de 8 y 11

9 es el primer número común que ocurre después de 8 y 11 en postorder y antes de 8 y 11 en preorder, por lo tanto 9 es la respuesta

• por ejemplo: 2

Antepasado mínimo común de 5,10

11,9,14,15,13,12,7 en postorder 7,3,1,0,2,6,4 en preorden

7 es el primer número que ocurre después de 5,10 en postorder y antes de 5,10 en preorder, por lo tanto, 7 es la respuesta

Si es un árbol binario completo con hijos del nodo x como 2 * x y 2 * x + 1, entonces hay una forma más rápida de hacerlo

int get_bits(unsigned int x) {
  int high = 31;
  int low = 0,mid;
  while(high>=low) {
    mid = (high+low)/2;
    if(1<<mid==x)
      return mid+1;
    if(1<<mid<x) {
      low = mid+1;
    }
    else {
      high = mid-1;
    }
  }
  if(1<<mid>x)
    return mid;
  return mid+1;
}

unsigned int Common_Ancestor(unsigned int x,unsigned int y) {

  int xbits = get_bits(x);
  int ybits = get_bits(y);
  int diff,kbits;
  unsigned int k;
  if(xbits>ybits) {
    diff = xbits-ybits;
    x = x >> diff;
  }
  else if(xbits<ybits) {
    diff = ybits-xbits;
    y = y >> diff;
  }
  k = x^y;
  kbits = get_bits(k);
  return y>>kbits;  
}

Como funciona

1. obtener bits necesarios para representar x & y que mediante la búsqueda binaria es O (log (32))
2. el prefijo común de notación binaria de x & y es el ancestro común
3. lo que esté representado por un mayor número de bits se lleva al mismo bit por k >> diff
4. k = x ^ y borra el prefijo común de x & y
5. encontrar bits que representan el sufijo restante
6. desplaza x o y por bits de sufijo para obtener el prefijo común que es el ancestro común.

Esto funciona porque básicamente divide el número más grande entre dos recursivamente hasta que ambos números sean iguales. Ese número es el ancestro común. Dividir es efectivamente la operación de turno correcta. Entonces necesitamos encontrar el prefijo común de dos números para encontrar el antepasado más cercano

En scala, puedes:

  abstract class Tree
  case class Node(a:Int, left:Tree, right:Tree) extends Tree
  case class Leaf(a:Int) extends Tree

  def lca(tree:Tree, a:Int, b:Int):Tree = {
    tree match {
      case Node(ab,l,r) => {
        if(ab==a || ab ==b) tree else {
          val temp = lca(l,a,b);
          val temp2 = lca(r,a,b);
          if(temp!=null && temp2 !=null)
            tree
          else if (temp==null && temp2==null)
            null
          else if (temp==null) r else l
        }

      }
      case Leaf(ab) => if(ab==a || ab ==b) tree else null
    }
  }

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null || root == p || root == q){
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        return left == null ? right : right == null ? left : root;
    }

Aquí está la forma C ++ de hacerlo. Intenté mantener el algoritmo lo más fácil posible de entender:

// Assuming that `BinaryNode_t` has `getData()`, `getLeft()` and `getRight()`
class LowestCommonAncestor
{
  typedef char type;    
  // Data members which would behave as place holders
  const BinaryNode_t* m_pLCA;
  type m_Node1, m_Node2;

  static const unsigned int TOTAL_NODES = 2;

  // The core function which actually finds the LCA; It returns the number of nodes found
  // At any point of time if the number of nodes found are 2, then it updates the `m_pLCA` and once updated, we have found it!
  unsigned int Search (const BinaryNode_t* const pNode)
  {
    if(pNode == 0)
      return 0;

    unsigned int found = 0;

    found += (pNode->getData() == m_Node1);
    found += (pNode->getData() == m_Node2);

    found += Search(pNode->getLeft()); // below condition can be after this as well
    found += Search(pNode->getRight());

    if(found == TOTAL_NODES && m_pLCA == 0)
      m_pLCA = pNode;  // found !

    return found;
  }

public:
  // Interface method which will be called externally by the client
  const BinaryNode_t* Search (const BinaryNode_t* const pHead,
                              const type node1,
                              const type node2)
  {
    // Initialize the data members of the class
    m_Node1 = node1;
    m_Node2 = node2;
    m_pLCA = 0;

    // Find the LCA, populate to `m_pLCANode` and return
    (void) Search(pHead);
    return m_pLCA;
  }
};

Cómo usarlo:

LowestCommonAncestor lca;
BinaryNode_t* pNode = lca.Search(pWhateverBinaryTreeNodeToBeginWith);
if(pNode != 0)
  ...

La forma más fácil de encontrar el Ancestro común más bajo es usar el siguiente algoritmo:

Examinar nodo raíz

si valor1 y valor2 son estrictamente menores que el valor en el nodo raíz 
    Examinar subárbol izquierdo
de lo contrario, si value1 y value2 son estrictamente mayores que el valor en el nodo raíz 
    Examinar subárbol derecho
más
    raíz de retorno

public int LCA(TreeNode root, int value 1, int value 2) {
    while (root != null) {
       if (value1 < root.data && value2 < root.data)
           return LCA(root.left, value1, value2);
       else if (value2 > root.data && value2 2 root.data)
           return LCA(root.right, value1, value2);
       else
           return root
    }

    return null;
} 

Encontre una solucion

1. Tomar orden
2. Toma preordenar
3. Tomar postorder

Dependiendo de 3 recorridos, puede decidir quién es el LCA. Desde LCA encuentre la distancia de ambos nodos. Agregue estas dos distancias, que es la respuesta.

Esto es lo que pienso.

1. Encuentre la ruta para el nodo de puño, guárdelo en arr1.
2. Comience a encontrar la ruta para el nodo 2, mientras lo hace, verifique cada valor desde la raíz hasta arr1.
3. momento en que el valor difiere, salir. El antiguo valor coincidente es el LCA.

Complejidad: paso 1: O (n), paso 2 = ~ O (n), total = ~ O (n).

Aquí hay dos enfoques en c # (.net) (ambos discutidos anteriormente) como referencia:

1. Versión recursiva de encontrar LCA en árbol binario (O (N), ya que como máximo se visita cada nodo) (los puntos principales de la solución es que LCA es (a) único nodo en árbol binario donde ambos elementos residen a ambos lados de los subárboles (izquierda y derecha) es LCA. (b) Y tampoco importa qué nodo esté presente en ambos lados: inicialmente intenté mantener esa información, y obviamente la función recursiva se volvió tan confusa. Una vez que me di cuenta, se volvió muy elegante.

2. Buscar ambos nodos (O (N)) y realizar un seguimiento de las rutas (usa espacio adicional, por lo tanto, el n. ° 1 es probablemente superior, incluso aunque el espacio sea insignificante si el árbol binario está bien equilibrado, ya que el consumo de memoria adicional será solo en O (log (N)).

   para que las rutas se comparen (esencialmente similar a la respuesta aceptada, pero las rutas se calculan asumiendo que el nodo del puntero no está presente en el nodo del árbol binario)

3. Solo para completar ( no relacionado con la pregunta ), LCA en BST (O (log (N))

4. Pruebas

Recursivo:

private BinaryTreeNode LeastCommonAncestorUsingRecursion(BinaryTreeNode treeNode, 
            int e1, int e2)
        {
            Debug.Assert(e1 != e2);
            
            if(treeNode == null)
            {
                return null;
            }
            if((treeNode.Element == e1)
                || (treeNode.Element == e2))
            {
                //we don't care which element is present (e1 or e2), we just need to check 
                //if one of them is there
                return treeNode;
            }
            var nLeft = this.LeastCommonAncestorUsingRecursion(treeNode.Left, e1, e2);
            var nRight = this.LeastCommonAncestorUsingRecursion(treeNode.Right, e1, e2);
            if(nLeft != null && nRight != null)
            {
                //note that this condition will be true only at least common ancestor
                return treeNode;
            }
            else if(nLeft != null)
            {
                return nLeft;
            }
            else if(nRight != null)
            {
                return nRight;
            }
            return null;
        }

donde la versión recursiva privada anterior se invoca mediante el siguiente método público:

public BinaryTreeNode LeastCommonAncestorUsingRecursion(int e1, int e2)
        {
            var n = this.FindNode(this._root, e1);
            if(null == n)
            {
                throw new Exception("Element not found: " + e1);
            }
            if (e1 == e2)
            {   
                return n;
            }
            n = this.FindNode(this._root, e2);
            if (null == n)
            {
                throw new Exception("Element not found: " + e2);
            }
            var node = this.LeastCommonAncestorUsingRecursion(this._root, e1, e2);
            if (null == node)
            {
                throw new Exception(string.Format("Least common ancenstor not found for the given elements: {0},{1}", e1, e2));
            }
            return node;
        }

Solución haciendo un seguimiento de las rutas de ambos nodos:

public BinaryTreeNode LeastCommonAncestorUsingPaths(int e1, int e2)
        {
            var path1 = new List<BinaryTreeNode>();
            var node1 = this.FindNodeAndPath(this._root, e1, path1);
            if(node1 == null)
            {
                throw new Exception(string.Format("Element {0} is not found", e1));
            }
            if(e1 == e2)
            {
                return node1;
            }
            List<BinaryTreeNode> path2 = new List<BinaryTreeNode>();
            var node2 = this.FindNodeAndPath(this._root, e2, path2);
            if (node1 == null)
            {
                throw new Exception(string.Format("Element {0} is not found", e2));
            }
            BinaryTreeNode lca = null;
            Debug.Assert(path1[0] == this._root);
            Debug.Assert(path2[0] == this._root);
            int i = 0;
            while((i < path1.Count)
                && (i < path2.Count)
                && (path2[i] == path1[i]))
            {
                lca = path1[i];
                i++;
            }
            Debug.Assert(null != lca);
            return lca;
        }

donde FindNodeAndPath se define como

private BinaryTreeNode FindNodeAndPath(BinaryTreeNode node, int e, List<BinaryTreeNode> path)
        {
            if(node == null)
            {
                return null;
            }
            if(node.Element == e)
            {
                path.Add(node);
                return node;
            }
            var n = this.FindNodeAndPath(node.Left, e, path);
            if(n == null)
            {
                n = this.FindNodeAndPath(node.Right, e, path);
            }
            if(n != null)
            {
                path.Insert(0, node);
                return n;
            }
            return null;
        }

BST (LCA): no relacionado (solo para completar como referencia)

public BinaryTreeNode BstLeastCommonAncestor(int e1, int e2)
        {
            //ensure both elements are there in the bst
            var n1 = this.BstFind(e1, throwIfNotFound: true);
            if(e1 == e2)
            {
                return n1;
            }
            this.BstFind(e2, throwIfNotFound: true);
            BinaryTreeNode leastCommonAcncestor = this._root;
            var iterativeNode = this._root;
            while(iterativeNode != null)
            {
                if((iterativeNode.Element > e1 ) && (iterativeNode.Element > e2))
                {
                    iterativeNode = iterativeNode.Left;
                }
                else if((iterativeNode.Element < e1) && (iterativeNode.Element < e2))
                {
                    iterativeNode = iterativeNode.Right;
                }
                else
                {
                    //i.e; either iterative node is equal to e1 or e2 or in between e1 and e2
                    return iterativeNode;
                }
            }
            //control will never come here
            return leastCommonAcncestor;
        }

Pruebas unitarias

[TestMethod]
        public void LeastCommonAncestorTests()
        {
            int[] a = { 13, 2, 18, 1, 5, 17, 20, 3, 6, 16, 21, 4, 14, 15, 25, 22, 24 };
            int[] b = { 13, 13, 13, 2, 13, 18, 13, 5, 13, 18, 13, 13, 14, 18, 25, 22};
            BinarySearchTree bst = new BinarySearchTree();
            foreach (int e in a)
            {
                bst.Add(e);
                bst.Delete(e);
                bst.Add(e);
            }
            for(int i = 0; i < b.Length; i++)
            {
                var n = bst.BstLeastCommonAncestor(a[i], a[i + 1]);
                Assert.IsTrue(n.Element == b[i]);
                var n1 = bst.LeastCommonAncestorUsingPaths(a[i], a[i + 1]);
                Assert.IsTrue(n1.Element == b[i]);
                Assert.IsTrue(n == n1);
                var n2 = bst.LeastCommonAncestorUsingRecursion(a[i], a[i + 1]);
                Assert.IsTrue(n2.Element == b[i]);
                Assert.IsTrue(n2 == n1);
                Assert.IsTrue(n2 == n);
            }
        }

Si alguien interesado en pseudocódigo (para trabajos en el hogar universitario) aquí hay uno.

GETLCA(BINARYTREE BT, NODE A, NODE  B)
IF Root==NIL
    return NIL
ENDIF

IF Root==A OR root==B
    return Root
ENDIF

Left = GETLCA (Root.Left, A, B)
Right = GETLCA (Root.Right, A, B)

IF Left! = NIL AND Right! = NIL
    return root
ELSEIF Left! = NIL
    Return Left
ELSE
    Return Right
ENDIF

Aunque esto ya ha sido respondido, este es mi enfoque para este problema usando el lenguaje de programación C. Aunque el código muestra un árbol de búsqueda binario (en lo que respecta a insert ()), el algoritmo también funciona para un árbol binario. La idea es repasar todos los nodos que se encuentran desde el nodo A al nodo B en el recorrido transversal, buscar los índices para estos en el recorrido del orden posterior. El nodo con el índice máximo en el recorrido de orden posterior es el ancestro común más bajo.

Este es un código C que funciona para implementar una función para encontrar el ancestro común más bajo en un árbol binario. También proporciono todas las funciones de utilidad, etc., pero salte a CommonAncestor () para una comprensión rápida.

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <math.h>

static inline int min (int a, int b)
{
    return ((a < b) ? a : b);
}
static inline int max (int a, int b)
{
    return ((a > b) ? a : b);
}

typedef struct node_ {
    int value;
    struct node_ * left;
    struct node_ * right;
} node;

#define MAX 12

int IN_ORDER[MAX] = {0};
int POST_ORDER[MAX] = {0};

createNode(int value) 
{
    node * temp_node = (node *)malloc(sizeof(node));
    temp_node->left = temp_node->right = NULL;
    temp_node->value = value;
    return temp_node;
}

node *
insert(node * root, int value)
{
    if (!root) {
        return createNode(value);
    }

    if (root->value > value) {
        root->left = insert(root->left, value);
    } else {
        root->right = insert(root->right, value);
    }

    return root;
}


/* Builds inorder traversal path in the IN array */
void
inorder(node * root, int * IN)
{
    static int i = 0;

    if (!root) return;

    inorder(root->left, IN);
    IN[i] = root->value;
    i++;
    inorder(root->right, IN);
}

/* Builds post traversal path in the POST array */

void
postorder (node * root, int * POST)
{
    static int i = 0;

    if (!root) return;

    postorder(root->left, POST);
    postorder(root->right, POST);
    POST[i] = root->value;
    i++;
}


int
findIndex(int * A, int value)
{
    int i = 0;
    for(i = 0; i< MAX; i++) {
        if(A[i] == value) return i;
    }
}
int
CommonAncestor(int val1, int val2)
{
    int in_val1, in_val2;
    int post_val1, post_val2;
    int j=0, i = 0; int max_index = -1;

    in_val1 = findIndex(IN_ORDER, val1);
    in_val2 = findIndex(IN_ORDER, val2);
    post_val1 = findIndex(POST_ORDER, val1);
    post_val2 = findIndex(POST_ORDER, val2);

    for (i = min(in_val1, in_val2); i<= max(in_val1, in_val2); i++) {
        for(j = 0; j < MAX; j++) {
            if (IN_ORDER[i] == POST_ORDER[j]) {
                if (j > max_index) {
                    max_index = j;
                }
            }
        }
    }
    printf("\ncommon ancestor of %d and %d is %d\n", val1, val2, POST_ORDER[max_index]);
    return max_index;
}
int main()
{
    node * root = NULL; 

    /* Build a tree with following values */
    //40, 20, 10, 30, 5, 15, 25, 35, 1, 80, 60, 100
    root = insert(root, 40);
    insert(root, 20);
    insert(root, 10);
    insert(root, 30);
    insert(root, 5);
    insert(root, 15);
    insert(root, 25);
    insert(root, 35);
    insert(root, 1);
    insert(root, 80);
    insert(root, 60);
    insert(root, 100);

    /* Get IN_ORDER traversal in the array */
    inorder(root, IN_ORDER);

    /* Get post order traversal in the array */
    postorder(root, POST_ORDER);

    CommonAncestor(1, 100);


}

Puede haber un enfoque más. Sin embargo, no es tan eficiente como el que ya se sugirió en las respuestas.

• Cree un vector de ruta para el nodo n1.

• Cree un segundo vector de ruta para el nodo n2.

• El vector de ruta implica que los nodos establecidos desde ese atravesarían para alcanzar el nodo en cuestión.

• Compara ambos vectores de ruta. El índice donde no coinciden, devuelve el nodo en ese índice - 1. Esto daría el LCA.

Contras para este enfoque:

Necesita atravesar el árbol dos veces para calcular los vectores de ruta. Necesita espacio adicional O (h) para almacenar vectores de ruta.

Sin embargo, esto también es fácil de implementar y comprender.

Código para calcular el vector de ruta:

private boolean findPathVector (TreeNode treeNode, int key, int pathVector[], int index) {

        if (treeNode == null) {
            return false;
        }

        pathVector [index++] = treeNode.getKey ();

        if (treeNode.getKey () == key) {
            return true;
        }
        if (findPathVector (treeNode.getLeftChild (), key, pathVector, index) || 
            findPathVector (treeNode.getRightChild(), key, pathVector, index)) {

            return true;        
        }

        pathVector [--index] = 0;
        return false;       
    }

Intenta así

node * lca(node * root, int v1,int v2)
{

if(!root) {
            return NULL;
    }
    if(root->data == v1 || root->data == v2) {
        return root;}
    else
    {
        if((v1 > root->data && v2 < root->data) || (v1 < root->data && v2 > root->data))
        {
            return root;
        }

        if(v1 < root->data && v2 < root->data)
        {
            root = lca(root->left, v1, v2);
        }

        if(v1 > root->data && v2 > root->data)
        {
            root = lca(root->right, v1, v2);
        }
    }
return root;
}

Forma cruda:

• En cada nodo
  • X = encontrar si alguno de los n1, n2 existe en el lado izquierdo del nodo
  • Y = buscar si alguno de los n1, n2 existe en el lado derecho del nodo
    • si el nodo en sí es n1 || n2, podemos llamarlo encontrado a la izquierda o a la derecha para fines de generalización.
  • Si tanto X como Y son verdaderas, entonces el Nodo es la CA

El problema con el método anterior es que haremos el "hallazgo" varias veces, es decir, existe la posibilidad de que cada nodo sea atravesado varias veces. Podemos superar este problema si podemos registrar la información para no procesarla nuevamente (piense en la programación dinámica).

Entonces, en lugar de buscar cada nodo, mantenemos un registro de lo que ya se ha encontrado.

Mejor manera:

• Verificamos si para un nodo dado si left_set (lo que significa que n1 | n2 se ha encontrado en el subárbol izquierdo) o right_set en profundidad en primer lugar. (NOTA: Le estamos dando a la raíz la propiedad de ser left_set si es n1 | n2)
• Si ambos, left_set y right_set, el nodo es un LCA.

Código:

struct Node *
findCA(struct Node *root, struct Node *n1, struct Node *n2, int *set) {
   int left_set, right_set;
   left_set = right_set = 0;
   struct Node *leftCA, *rightCA;
   leftCA = rightCA = NULL;

   if (root == NULL) {
      return NULL;
   }
   if (root == n1 || root == n2) {
      left_set = 1;
      if (n1 == n2) {
         right_set = 1;
      }
   }

   if(!left_set) {
      leftCA = findCA(root->left, n1, n2, &left_set);
      if (leftCA) {
         return leftCA;
      }
   }
   if (!right_set) {
      rightCA= findCA(root->right, n1, n2, &right_set);
      if(rightCA) {
         return rightCA;
      }
   }

   if (left_set && right_set) {
      return root;
   } else {
      *set = (left_set || right_set);
      return NULL;
   }
}

Código para A Breadth First Search para asegurarse de que ambos nodos estén en el árbol. Solo entonces avance con la búsqueda de LCA. Comente si tiene alguna sugerencia para mejorar. Creo que probablemente podamos marcarlos como visitados y reiniciar la búsqueda en un punto determinado donde lo dejamos para mejorar para el segundo nodo (si no se encuentra VISITADO)

public class searchTree {
    static boolean v1=false,v2=false;
    public static boolean bfs(Treenode root, int value){
         if(root==null){
           return false;
     }
    Queue<Treenode> q1 = new LinkedList<Treenode>();

    q1.add(root);
    while(!q1.isEmpty())
    {
        Treenode temp = q1.peek();

        if(temp!=null) {
            q1.remove();
            if (temp.value == value) return true;
            if (temp.left != null) q1.add(temp.left);
            if (temp.right != null) q1.add(temp.right);
        }
    }
    return false;

}
public static Treenode lcaHelper(Treenode head, int x,int y){

    if(head==null){
        return null;
    }

    if(head.value == x || head.value ==y){
        if (head.value == y){
            v2 = true;
            return head;
        }
        else {
            v1 = true;
            return head;
        }
    }

    Treenode left = lcaHelper(head.left, x, y);
    Treenode right = lcaHelper(head.right,x,y);

    if(left!=null && right!=null){
        return head;
    }
    return (left!=null) ? left:right;
}

public static int lca(Treenode head, int h1, int h2) {
    v1 = bfs(head,h1);
    v2 = bfs(head,h2);
    if(v1 && v2){
        Treenode lca = lcaHelper(head,h1,h2);
        return lca.value;
    }
    return -1;
}
}

Tiene razón en que sin un nodo principal, la solución con recorrido le dará O (n) complejidad de tiempo.

Enfoque transversal Suponga que está encontrando LCA para los nodos A y B, el enfoque más directo es obtener primero la ruta de la raíz a A y luego obtener la ruta de la raíz a B. Una vez que tenga estas dos rutas, puede iterar fácilmente sobre ellas. y encuentre el último nodo común, que es el ancestro común más bajo de A y B.

Solución recursiva Otro enfoque es utilizar la recursividad. Primero, podemos obtener LCA tanto del árbol izquierdo como del árbol derecho (si existe). Si A o B es el nodo raíz, entonces la raíz es el LCA y simplemente devolvemos la raíz, que es el punto final de la recursión. A medida que sigamos dividiendo el árbol en subárboles, eventualmente golpearemos A y B.

Para combinar soluciones de subproblemas, si LCA (árbol izquierdo) devuelve un nodo, sabemos que tanto A como B se ubican en el árbol izquierdo y el nodo devuelto es el resultado final. Si tanto LCA (izquierda) como LCA (derecha) devuelven nodos no vacíos, significa que A y B están en el árbol izquierdo y derecho respectivamente. En este caso, el nodo raíz es el nodo común más bajo.

Verifique el Ancestro común más bajo para obtener un análisis detallado y una solución.

Algunas de las soluciones aquí asumen que hay referencia al nodo raíz, algunas asumen que el árbol es un BST. Compartir mi solución usando hashmap, sin referencia al rootnodo y al árbol puede ser BST o no BST:

    var leftParent : Node? = left
    var rightParent : Node? = right
    var map = [data : Node?]()

    while leftParent != nil {
        map[(leftParent?.data)!] = leftParent
        leftParent = leftParent?.parent
    }

    while rightParent != nil {
        if let common = map[(rightParent?.data)!] {
            return common
        }
        rightParent = rightParent?.parent
    }

Solución 1: Recursivo - Más rápido

• La idea es atravesar el árbol a partir de la raíz. Si alguna de las claves dadas p y q coincide con la raíz, entonces la raíz es LCA, suponiendo que ambas claves estén presentes. Si la raíz no coincide con ninguna de las claves, recurrimos para el subárbol izquierdo y derecho.
• El nodo que tiene una clave presente en su subárbol izquierdo y la otra clave presente en el subárbol derecho es el LCA. Si ambas teclas se encuentran en el subárbol izquierdo, entonces el subárbol izquierdo también tiene LCA; de lo contrario, LCA se encuentra en el subárbol derecho.

• Complejidad de tiempo: O (n)
• Complejidad espacial: O (h) - para la pila de llamadas recursivas

class Solution 
{
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
    {
        if(root == null || root == p  || root == q)
            return root;

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if(left == null)
            return right;
        else if(right == null)
            return left;
        else
            return root;    // If(left != null && right != null)
    }
}

Solución 2: Iterativo - Uso de punteros principales - Más lento

• Crea una tabla hash vacía.
• Inserte p y todos sus antepasados ​​en la tabla hash.
• Compruebe si q o alguno de sus antepasados ​​existen en la tabla hash, en caso afirmativo, devuelva el primer antepasado existente.

• Complejidad de tiempo: O (n): en el peor de los casos, podríamos estar visitando todos los nodos del árbol binario.
• Complejidad del espacio: O (n): el espacio utilizaba el puntero principal Hash-table, ancestor_set y queue, serían O (n) cada uno.

class Solution
{
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
    {
        HashMap<TreeNode, TreeNode> parent_map = new HashMap<>();
        HashSet<TreeNode> ancestors_set = new HashSet<>();
        Queue<TreeNode> queue = new LinkedList<>();

        parent_map.put(root, null);
        queue.add(root);

        while(!parent_map.containsKey(p) || !parent_map.containsKey(q))
        {
            TreeNode node = queue.poll();

            if(node.left != null)
            {
                parent_map.put(node.left, node);
                queue.add(node.left);
            }
            if(node.right != null)
            {
                parent_map.put(node.right, node);
                queue.add(node.right);
            }
        }

        while(p != null)
        {
            ancestors_set.add(p);
            p = parent_map.get(p);
        }

        while(!ancestors_set.contains(q))
            q = parent_map.get(q);

        return q;
    }
}