Como encontrar o menor ancestral comum de dois nós em qualquer árvore binária?

A Árvore Binária aqui pode não ser necessariamente uma Árvore de Pesquisa Binária.
A estrutura pode ser tomada como -

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

A solução máxima que eu consegui encontrar com um amigo foi algo desse tipo -
considere esta árvore binária :

O percurso transversal da ordem produz - 8, 4, 9, 2, 5, 1, 6, 3, 7

E a passagem pós-ordem produz - 8, 9, 4, 5, 2, 6, 7, 3, 1

Por exemplo, se queremos encontrar o ancestral comum dos nós 8 e 5, fazemos uma lista de todos os nós que estão entre 8 e 5 na travessia da árvore de ordem de entrada, que neste caso é [4, 9 2] Em seguida, verificamos qual nó nesta lista aparece por último no percurso da ordem posterior, que é 2. Portanto, o ancestral comum de 8 e 5 é 2.

A complexidade desse algoritmo, creio, é O (n) (O (n) para travessias dentro / fora da ordem, o restante das etapas sendo novamente O (n), pois elas nada mais são do que simples iterações em matrizes). Mas há uma forte chance de que isso esteja errado. :-)

Mas essa é uma abordagem muito grosseira, e não tenho certeza se ela se quebra em alguns casos. Existe alguma outra solução (possivelmente mais ideal) para esse problema?

Nick Johnson está certo de que um algoritmo de complexidade de tempo O (n) é o melhor que você pode fazer se não tiver ponteiros pai.) Para uma versão recursiva simples desse algoritmo, veja o código na publicação de Kinding, que é executada em tempo O (n) .

Mas lembre-se de que, se seus nós tiverem ponteiros pai, um algoritmo aprimorado será possível. Para os dois nós em questão, construa uma lista contendo o caminho da raiz para o nó, iniciando no nó e inserindo o pai com uma frente.

Portanto, no exemplo 8, você obtém (mostrando as etapas): {4}, {2, 4}, {1, 2, 4}

Faça o mesmo para o outro nó em questão, resultando em (etapas não mostradas): {1, 2}

Agora compare as duas listas criadas procurando o primeiro elemento em que a lista difere ou o último elemento de uma das listas, o que ocorrer primeiro.

Este algoritmo requer tempo O (h) em que h é a altura da árvore. No pior caso, O (h) é equivalente a O (n), mas se a árvore estiver equilibrada, isso é apenas O (log (n)). Também requer espaço O (h). É possível uma versão aprimorada que utilize apenas espaço constante, com o código mostrado no post do CEGRD

Independentemente de como a árvore é construída, se esta for uma operação que você executa muitas vezes na árvore sem alterá-la, existem outros algoritmos que você pode usar que requerem preparação do tempo O (n) [linear], mas depois encontram qualquer par leva apenas tempo O (1) [constante]. Para referências a esses algoritmos, consulte a página com problemas mais baixos de ancestrais comuns na Wikipedia . (Agradecemos a Jason por postar originalmente este link)

Iniciando a partir do rootnó e movendo-se para baixo, se você encontrar algum nó que tenha pou qcomo filho direto, é o LCA. (editar - este deve ser se pou qfor o valor do nó, retorne-o. Caso contrário, falhará quando um de pou qfor um filho direto do outro.)

Caso pcontrário, se você encontrar um nó na subárvore direita (ou esquerda) e qna subárvore esquerda (ou direita), será o LCA.

O código fixo se parece com:

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;
                }
        }
}

O código abaixo falha quando um deles é filho direto de outro.

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 em ação

Aqui está o código de trabalho em 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; 
}

As respostas dadas até agora usam recursão ou armazenam, por exemplo, um caminho na memória.

Ambas as abordagens podem falhar se você tiver uma árvore muito profunda.

Aqui está minha opinião sobre essa questão. Quando verificamos a profundidade (distância da raiz) de ambos os nós, se forem iguais, podemos mover com segurança para cima dos dois nós em direção ao ancestral comum. Se uma das profundidades for maior, devemos mover para cima a partir do nó mais profundo enquanto permanecermos no outro.

Aqui está o 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;    

A complexidade do tempo desse algoritmo é: O (n). A complexidade do espaço desse algoritmo é: O (1).

Em relação ao cálculo da profundidade, podemos primeiro lembrar a definição: Se v é raiz, profundidade (v) = 0; Caso contrário, profundidade (v) = profundidade (pai (v)) + 1. Podemos calcular a profundidade da seguinte forma:

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

Bem, isso depende da estrutura da sua árvore binária. Presumivelmente, você tem alguma maneira de encontrar o nó da folha desejado, dada a raiz da árvore - basta aplicar isso a ambos os valores até que os galhos escolhidos divergam.

Se você não tem como encontrar a folha desejada, dada a raiz, sua única solução - tanto na operação normal quanto no último nó comum - é uma busca de força bruta na árvore.

Isso pode ser encontrado em: - 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;
        }
    }
}

O algoritmo de ancestrais menos comuns off-line de Tarjan é bom o suficiente (cf. também Wikipedia ). Há mais sobre o problema (o menor problema ancestral comum) na Wikipedia .

Para descobrir o ancestral comum de dois nós: -

• Localize o nó Nó1 na árvore usando a pesquisa binária e salve todos os nós visitados neste processo em uma matriz, digamos A1. Tempo - O (logn), Espaço - O (logn)
• Encontre o Nó2 especificado na árvore usando a pesquisa binária e salve todos os nós visitados neste processo em uma matriz, por exemplo A2. Tempo - O (logn), Espaço - O (logn)
• Se a lista A1 ou A2 estiver vazia, então um nó não existe e, portanto, não há ancestral comum.
• Se a lista A1 e a lista A2 não estiverem vazias, procure na lista até encontrar o nó não correspondente. Assim que você encontrar esse nó, o nó anterior a esse é ancestral comum.

Isso funcionaria para a árvore de pesquisa binária.

Fiz uma tentativa com imagens ilustrativas e código de trabalho em Java,

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

O algoritmo recursivo abaixo será executado em O (log N) para uma árvore binária balanceada. Se um dos nós passados ​​para a função getLCA () for o mesmo que a raiz, a raiz será o LCA e não haverá necessidade de executar nenhuma recussão.

Casos de teste. [1] Ambos os nós n1 e n2 estão na árvore e residem em ambos os lados do nó pai. [2] O nó n1 ou n2 é a raiz, o LCA é a raiz. [3] Somente n1 ou n2 está na árvore, o LCA será o nó raiz da subárvore esquerda da raiz da árvore ou o LCA será o nó raiz da subárvore direita da raiz da árvore.

[4] Nem n1 nem n2 estão na árvore, não há ACV. [5] Ambos n1 e n2 estão em uma linha reta um ao lado do outro, o LCA será um dos n1 ou n2 que está sempre próximo à raiz da árvore.

//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);
}

Apenas desça da árvore inteira, rootdesde que os dois nós, digamos, pe qpara os quais o Ancestor seja encontrado, estejam na mesma subárvore (o que significa que seus valores são menores ou maiores que os da raiz).

Isso caminha diretamente da raiz para o menos ancestral comum, sem olhar para o resto da árvore, por isso é praticamente o mais rápido possível. Algumas maneiras de fazer isso.

Iterativo, espaço O (1)

Pitão

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;
}

em caso de estouro, eu faria (root.val - (long) p.val) * (root.val - (long) q.val)

Recursivo

Pitão

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
}

Considere esta árvore

Se fizermos a travessia pós-encomenda e pré-encomenda e encontrarmos o primeiro predecessor e sucessor comum, obteremos o ancestral comum.

pós-encomenda => 0,2,1,5,4,6,3,8,10,11,9,14,15,13,12,7 pré-encomenda => 7,3,1,0,2,6,4 5,12,9,8,11,10,13,15,14

• por exemplo: 1

Ancestral menos comum de 8,11

em pós-encomenda temos => 9,14,15,13,12,7 após 8 e 11 em pré-encomenda temos => 7,3,1,0,2,6,4,5,12,9 antes de 8 e 11

9 é o primeiro número comum que ocorre após 8 e 11 na pós-encomenda e antes de 8 e 11 na pré-encomenda, portanto 9 é a resposta

• por exemplo: 2

Menos ancestral comum de 5,10

11,9,14,15,13,12,7 na pré-encomenda 7,3,1,0,2,6,4 na pré-encomenda

7 é o primeiro número que ocorre após 5,10 na pós-encomenda e antes de 5,10 na pré-encomenda, portanto 7 é a resposta

Se for uma árvore binária completa com filhos do nó x como 2 * x e 2 * x + 1, haverá uma maneira mais rápida de fazê-lo.

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. obter bits necessários para representar x & y que usando pesquisa binária é O (log (32))
2. o prefixo comum da notação binária de x e y é o ancestral comum
3. o que for representado por um maior número de bits é trazido para o mesmo bit por k >> diff
4. k = x ^ y apaga o prefixo comum de x & y
5. encontre bits representando o sufixo restante
6. desloque x ou y por bits de sufixo para obter o prefixo comum, que é o ancestral comum.

Isso funciona porque basicamente divide o número maior por dois recursivamente até que ambos os números sejam iguais. Esse número é o ancestral comum. Dividir é efetivamente a operação de turno certo. Então, precisamos encontrar um prefixo comum de dois números para encontrar o ancestral mais próximo

No scala, você pode:

  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;
    }

Aqui está a maneira C ++ de fazer isso. Tentaram manter o algoritmo o mais fácil possível para 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;
  }
};

Como usá-lo:

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

A maneira mais fácil de encontrar o antepassado comum mais baixo é usando o seguinte algoritmo:

Examine o nó raiz

se value1 e value2 forem estritamente menores que o valor no nó raiz 
    Examinar subárvore esquerda
caso contrário, se value1 e value2 forem estritamente maiores que o valor no nó raiz 
    Examine a subárvore direita
outro
    raiz 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;
} 

Eu encontrei uma solução

1. Tomar em ordem
2. Fazer pré-encomenda
3. Fazer pós-encomenda

Dependendo de três percursos, você pode decidir quem é o LCA. No LCA, encontre a distância dos dois nós. Adicione essas duas distâncias, que é a resposta.

Aqui está o que eu penso,

1. Encontre a rota para o primeiro nó, armazene-a em arr1.
2. Comece a encontrar a rota para o nó 2, enquanto faz isso, verifique todos os valores da raiz ao arr1.
3. Quando o valor for diferente, saia. O antigo valor correspondente é o LCA.

Complexidade: passo 1: O (n), passo 2 = ~ O (n), total = ~ O (n).

Aqui estão duas abordagens em c # (.net) (ambas discutidas acima) para referência:

1. Versão recursiva de localização de LCA na árvore binária (O (N) - como no máximo cada nó é visitado) (os principais pontos da solução é LCA é (a) único nó na árvore binária em que ambos os elementos residem nos dois lados das subárvores (esquerda e à direita) é LCA. (b) E também não importa qual nó está presente em ambos os lados - inicialmente eu tentei manter essas informações e, obviamente, a função recursiva se tornou tão confusa.Depois que percebi, ficou muito elegante.

2. Pesquisando ambos os nós (O (N)) e mantendo o controle de caminhos (usa espaço extra -, o número 1 é provavelmente superior, mesmo que o espaço seja provavelmente insignificante se a árvore binária estiver bem equilibrada, pois o consumo de memória extra será apenas O (log (N)).

   para que os caminhos sejam comparados (essencialmente semelhantes à resposta aceita - mas os caminhos são calculados assumindo que o nó do ponteiro não está presente no nó da árvore binária)

3. Apenas para a conclusão ( não relacionada à pergunta ), LCA no BST (O (log (N))

4. Testes

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;
        }

onde a versão recursiva privada acima é invocada pelo seguinte 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;
        }

Solução, acompanhando os caminhos dos dois nós:

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;
        }

onde FindNodeAndPath é definido 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) - não relacionado (apenas para conclusão para referência)

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;
        }

Testes unitários

[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);
            }
        }

Se alguém interessado em pseudo-código (para trabalhos domésticos em universidades), aqui está um.

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

Embora isso já tenha sido respondido, esta é minha abordagem para esse problema usando a linguagem de programação C. Embora o código mostre uma árvore de pesquisa binária (no que diz respeito a insert ()), o algoritmo também funciona para uma árvore binária. A idéia é passar por todos os nós que se encontram do nó A ao nó B no percurso em ordem, procurando os índices para eles no percurso pós-ordem. O nó com índice máximo na travessia pós-ordem é o menor ancestral comum.

Este é um código C em funcionamento para implementar uma função para encontrar o menor ancestral comum em uma árvore binária. Também estou fornecendo todas as funções utilitárias, etc., mas pule para CommonAncestor () para entender rapidamente.

#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);


}

Pode haver mais uma abordagem. No entanto, não é tão eficiente quanto o já sugerido nas respostas.

• Crie um vetor de caminho para o nó n1.

• Crie um segundo vetor de caminho para o nó n2.

• Vetor de caminho que implica os nós definidos a partir daquele que seria percorrido para alcançar o nó em questão.

• Compare os dois vetores de caminho. O índice em que são incompatíveis retorna o nó nesse índice - 1. Isso daria o LCA.

Contras para esta abordagem:

Precisa percorrer a árvore duas vezes para calcular os vetores do caminho. Precisa de espaço O (h) adicional para armazenar vetores de caminho.

No entanto, isso é fácil de implementar e entender também.

Código para calcular o vetor de caminho:

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;       
    }

Tente assim

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;
}

Maneira bruta:

• Em cada nó
  • X = encontre se um dos n1, n2 existe no lado esquerdo do nó
  • Y = encontre se um dos n1, n2 existe no lado direito do nó
    • se o próprio nó for n1 || n2, podemos chamá-lo ou encontrado à esquerda ou à direita para fins de generalização.
  • Se X e Y forem verdadeiros, o Nó é a CA

O problema com o método acima é que faremos o "find" várias vezes, ou seja, existe a possibilidade de cada nó ser percorrido várias vezes. Podemos superar esse problema se conseguirmos registrar as informações para não processá-las novamente (pense em programação dinâmica).

Portanto, em vez de encontrar todos os nós, mantemos um registro do que já foi encontrado.

Melhor maneira:

• Verificamos se, para um determinado nó, se left_set (ou seja, n1 | n2 foi encontrado na subárvore esquerda) ou right_set de maneira profunda, primeiro. (NOTA: Estamos dando à própria raiz a propriedade de ser left_set se for n1 | n2)
• Se left_set e right_set, o nó é um 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 uma primeira amplitude de pesquisa para garantir que ambos os nós estejam na árvore. Somente então avance com a pesquisa LCA. Por favor, comente se você tem alguma sugestão para melhorar. Acho que provavelmente podemos marcá-los como visitados e reiniciar a pesquisa em um determinado ponto em que paramos para melhorar o segundo nó (se ele não for encontrado VISITE)

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;
}
}

Você está certo de que, sem um nó pai, a solução com travessia fornecerá complexidade de tempo O (n).

Abordagem transversal Suponha que você esteja encontrando LCA para os nós A e B, a abordagem mais direta é primeiro obter o caminho da raiz para A e, em seguida, obter o caminho da raiz para B. Depois de ter esses dois caminhos, é possível iterá-los facilmente e encontre o último nó comum, que é o menor ancestral comum de A e B.

Solução recursiva Outra abordagem é usar a recursão. Primeiro, podemos obter LCA da árvore esquerda e da árvore direita (se existir). Se A ou B for o nó raiz, a raiz será o LCA e retornaremos a raiz, que é o ponto final da recursão. À medida que continuamos dividindo a árvore em subárvores, eventualmente, atingimos A e B.

Para combinar soluções de subproblemas, se LCA (árvore esquerda) retornar um nó, sabemos que A e B localizam na árvore esquerda e o nó retornado é o resultado final. Se LCA (esquerda) e LCA (direita) retornarem nós não vazios, significa que A e B estão na árvore esquerda e direita, respectivamente. Nesse caso, o nó raiz é o nó comum mais baixo.

Verifique o menor ancestral comum para análise e solução detalhadas.

Algumas das soluções aqui assumem que há referência ao nó raiz, outras assumem que a árvore é uma BST. Compartilhar minha solução usando o hashmap, sem referência ao rootnó e à árvore, pode ser BST ou não-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
    }

Solução 1: Recursiva - Mais Rápida

• A idéia é atravessar a árvore a partir da raiz. Se qualquer uma das teclas dadas p e q corresponder à raiz, a raiz será LCA, assumindo que ambas estejam presentes. Se o root não corresponder a nenhuma das chaves, recursamos pela subárvore esquerda e direita.
• O nó que tem uma chave presente na subárvore esquerda e a outra chave presente na subárvore direita é o LCA. Se ambas as chaves estiverem na subárvore esquerda, a subárvore esquerda também terá LCA, caso contrário, o LCA ficará na subárvore direita.

• Complexidade temporal: O (n)
• Complexidade do espaço: O (h) - para pilha de chamadas 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)
    }
}

Solução 2: Iterativo - Usando ponteiros pai - Mais lento

• Crie uma tabela de hash vazia.
• Insira p e todos os seus ancestrais na tabela de hash.
• Verifique se q ou algum de seus ancestrais existe na tabela de hash; se sim, retorne o primeiro ancestral existente.

• Complexidade do tempo: O (n) - No pior caso, podemos estar visitando todos os nós da árvore binária.
• Complexidade do espaço: O (n) - O espaço utilizado pelo ponteiro pai Hash-table, ancestor_set e fila, seria O (n) cada.

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;
    }
}