Como encontrar o antepassado comum mais baixo de dois nós em qualquer tree binária?

A Árvore Binária aqui pode não ser necessariamente uma Árvore de Busca Binária.
A estrutura poderia ser tomada como –

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

A solução máxima que eu poderia resolver com um amigo era algo desse tipo –
Considere esta tree binária :

Árvore binária http://sofpt.miximages.com/algorithm/img151.gif

A travessia interna produz – 8, 4, 9, 2, 5, 1, 6, 3, 7

E o traversal de pós-ordem rende – 8, 9, 4, 5, 2, 6, 7, 3, 1

Então, por exemplo, se quisermos encontrar o ancestral comum dos nós 8 e 5, então fazemos uma lista de todos os nós que estão entre 8 e 5 na travessia da tree dentro da ordem, que neste caso é [4, 9 2]. Em seguida, verificamos qual nó dessa lista aparece por último no percurso da pós-ordem, que é 2. Portanto, o ancestral comum para 8 e 5 é 2.

A complexidade para este algoritmo, acredito, é O (n) (O (n) para travessias de ordem / pós-ordem, sendo o restante das etapas novamente O (n), já que não são nada mais que simples iterações em matrizes). Mas há uma forte chance de que isso esteja errado. 🙂

Mas esta é uma abordagem muito grosseira, e não tenho certeza se ela se desfaz em algum caso. Existe alguma outra solução (possivelmente mais ideal) para este problema?

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

Mas tenha em mente que, se seus nós tiverem pointers pai, um algoritmo aprimorado será possível. Para ambos os nós em questão, construa uma lista contendo o caminho da raiz para o nó, iniciando no nó e inserindo o pai na frente.

Então, para 8 no seu exemplo, você começa (mostrando as etapas): {4}, {2, 4}, {1, 2, 4}

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

Agora compare as duas listas que você fez procurando o primeiro elemento onde a lista é diferente, ou o último elemento de uma das listas, o que ocorrer primeiro.

Esse algoritmo requer O (h) tempo em que h é a altura da tree. No pior caso, O (h) é equivalente a O (n), mas se a tree é balanceada, isso é somente O (log (n)). Também requer O (h) espaço. É possível uma versão melhorada que use apenas espaço constante, com o código mostrado no post do CEGRD


Independentemente de como a tree é construída, se esta for uma operação que você executa muitas vezes na tree sem alterá-la, existem outros algoritmos que podem ser usados ​​que requerem a preparação do tempo O (n) [linear], mas depois encontrar qualquer par leva apenas O (1) [constante] tempo. Para obter referências a esses algoritmos, consulte a página do menor problema de ancestral comum na Wikipedia . (Crédito ao Jason por postar originalmente este link)

A partir do nó root e movendo-se para baixo se você encontrar qualquer nó que tenha p ou q como seu filho direto, então é o LCA. (edit – isto deve ser se p ou q for o valor do nó, devolvê-lo. Caso contrário, falhará quando um dos p ou q for um filho direto do outro.)

Senão, se você encontrar um nó com p em sua subtree direita (ou esquerda) e q em sua subtree esquerda (ou direita), então é a 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 é o 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 recursion ou armazenam, por exemplo, um caminho na memory.

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

Aqui está a minha opinião sobre esta questão. Quando verificamos a profundidade (distância da raiz) de ambos os nós, se eles são iguais, então podemos nos mover com segurança para cima a partir dos dois nós em direção ao ancestral comum. Se uma das profundidades é maior, devemos nos mover para cima a partir do nó mais profundo, enquanto permanecemos 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 temporal deste algoritmo é: O (n). A complexidade espacial deste 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 de como sua Árvore Binária está estruturada. Provavelmente você tem alguma maneira de encontrar o nó da folha desejado, dada a raiz da tree – simplesmente aplique-a a ambos os valores até que as ramificações escolhidas sejam divergentes.

Se você não tem uma maneira de encontrar a folha desejada dada a raiz, então sua única solução – tanto na operação normal quanto para encontrar o último nó comum – é uma busca por força bruta da tree.

Isto 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:

  • Encontre o nó dado Node1 na tree 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 fornecido na tree usando a pesquisa binária e salve todos os nós visitados neste processo em uma matriz, como A2. Tempo – O (logn), Espaço – O (logn)
  • Se a lista A1 ou a lista A2 estiver vazia, então o nó não existe, portanto, não existe um ancestral comum.
  • Se a lista A1 e a lista A2 não estiverem vazias, procure na lista até encontrar um nó não correspondente. Assim que você encontrar tal nó, então o nó antes disso é um ancestral comum.

Isso funcionaria para a tree de pesquisa binária.

Eu 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 tree binária balanceada. Se qualquer um dos nós passados ​​para a function getLCA () for o mesmo que a raiz, a raiz será o LCA e não haverá necessidade de executar qualquer reconfiguração.

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

[4] Nem n1 nem n2 estão na tree, não há LCA. [5] Ambos n1 e n2 estão em linha reta um ao lado do outro, LCA será n1 ou n2, que é sempre fechado para a raiz da tree.

 //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 root da tree inteira, contanto que ambos os nós dados, digamos q , para os quais o Antepassado tenha que ser encontrado, estejam na mesma sub-tree (significando que seus valores são menores ou maiores que os da raiz).

Isso caminha direto da raiz para o Ancestral Menos Comum, sem olhar para o resto da tree, então é quase tão rápido quanto possível. Algumas maneiras de fazer isso.

Iterativo, O (1) espaço

Python

 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

Python

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

Em scala, o código é:

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

Se é uma tree binária completa com filhos do nó x como 2 * xe 2 * x + 1 do que existe 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< 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> 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 pelo maior número de bits é trazido para o mesmo bit por k >> diff
  4. k = x ^ y erazes prefixo comum de x & y
  5. encontrar bits representando o sufixo restante
  6. Desloque x ou y por sufixo bits para obter o prefixo comum que é o ancestral comum.

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

Aqui está a maneira C ++ de fazê-lo. Tentei 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 ancestral comum mais baixo é usar o seguinte algoritmo:

 Examine o nó raiz

 se valor1 e valor2 forem estritamente menores que o valor no nó raiz 
     Examine a subtree esquerda
 else se valor1 e valor2 forem estritamente maiores que o valor no nó raiz 
     Examine a subtree direita
 outro
     retorno de raiz
 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. Take inorder
  2. Tome a encomenda
  3. Pegue o pedido

Dependendo de 3 percursos, você pode decidir quem é o LCA. A partir da LCA, localize a distância de ambos os nós. Adicione estas duas distâncias, que é a resposta.

Considere esta tree insira a descrição da imagem aqui

Se fizermos uma ordenação pré-ordenada e pré-ordenada e encontrarmos o primeiro predecessor e sucessor comum, obtemos o ancestral comum.

pós-ordem => 0,2,1,5,4,6,3,8,10,11,9,14,15,13,12,7 Pré-ordem => 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

no pós-ordenamento temos => 9,14,15,13,12,7 após 8 e 11 na pré-ordem 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 no postorder e antes do 8 & 11 no preorder, portanto 9 é a resposta

  • por exemplo: 2

Ancestral menos comum de 5,10

11,9,14,15,13,12,7 em postorder 7,3,1,0,2,6,4 em pré-ordem

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

Aqui está o que eu penso

  1. Encontre a rota para o primeiro nó, armazene-o em arr1.
  2. Comece encontrando a rota para o nó 2, enquanto faz isso, verifique cada valor da raiz para arr1.
  3. momento em que o valor difere, saia. O valor correspondente antigo é o LCA.

Complexidade: etapa 1: O (n), etapa 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 encontrar LCA na tree binária (O (N) – como no máximo cada nó é visitado) (pontos principais da solução é LCA é (a) único nó na tree binária onde ambos os elementos residem em ambos os lados das subtrees e direita) é LCA (b) E também não importa qual nó está presente em ambos os lados – inicialmente eu tentei manter essa informação, e obviamente a function recursiva se tornou tão confusa, uma vez que eu percebi isso, ficou muito elegante.

  2. Pesquisando ambos os nós (O (N)), e mantendo o controle de caminhos (usa espaço extra – então, # 1 é provavelmente superior, mesmo que o espaço seja provavelmente desprezível se a tree binária for bem balanceada, O (log (N)).

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

  3. Apenas para a conclusão ( não relacionada à questão ), 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 acima da versão recursiva privada é invocada seguindo o 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, mantendo o controle de caminhos de ambos os nós:

 public BinaryTreeNode LeastCommonAncestorUsingPaths(int e1, int e2) { var path1 = new List(); 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 path2 = new List(); 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 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 { //ie; 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 em casa na universidade) 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 é a minha abordagem para esse problema usando a linguagem de programação C. Embora o código mostre uma tree de busca binária (no que diz respeito a insert ()), o algoritmo também funciona para uma tree binária. A idéia é percorrer todos os nós que se encontram do nó A ao nó B na passagem interna, procurando os índices para estes na travessia pós-ordem. O nó com índice máximo na travessia pós-ordem é o ancestral comum mais baixo.

Este é um código C funcional para implementar uma function para encontrar o antepassado comum mais baixo em uma tree binária. Eu estou fornecendo todas as funções de utilidade, etc., mas pule para CommonAncestor () para uma rápida compreensão.

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

There can be one more approach. However it is not as efficient as the one already suggested in answers.

  • Create a path vector for the node n1.

  • Create a second path vector for the node n2.

  • Path vector implying the set nodes from that one would traverse to reach the node in question.

  • Compare both path vectors. The index where they mismatch, return the node at that index – 1. This would give the LCA.

Cons for this approach:

Need to traverse the tree twice for calculating the path vectors. Need addtional O(h) space to store path vectors.

However this is easy to implement and understand as well.

Code for calculating the path vector:

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

Crude way:

  • At every node
    • X = find if either of the n1, n2 exist on the left side of the Node
    • Y = find if either of the n1, n2 exist on the right side of the Node
      • if the node itself is n1 || n2, we can call it either found on left or right for the purposes of generalization.
    • If both X and Y is true, then the Node is the CA

The problem with the method above is that we will be doing the “find” multiple times, ie there is a possibility of each node getting traversed multiple times. We can overcome this problem if we can record the information so as to not process it again (think dynamic programming).

So rather than doing find every node, we keep a record of as to whats already been found.

Better Way:

  • We check to see if for a given node if left_set (meaning either n1 | n2 has been found in the left subtree) or right_set in a depth first fashion. (NOTE: We are giving the root itself the property of being left_set if it is either n1 | n2)
  • If both left_set and right_set then the node is a 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; } } 

Code for A Breadth First Search to make sure both nodes are in the tree. Only then move forward with the LCA search. Please comment if you have any suggestions to improve. I think we can probably mark them visited and restart the search at a certain point where we left off to improve for the second node (if it isn’t found VISITED)

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

You are correct that without a parent node, solution with traversal will give you O(n) time complexity.

Traversal approach Suppose you are finding LCA for node A and B, the most straightforward approach is to first get the path from root to A and then get the path from root to B. Once you have these two paths, you can easily iterate over them and find the last common node, which is the lowest common ancestor of A and B.

Recursive solution Another approach is to use recursion. First, we can get LCA from both left tree and right tree (if exists). If the either of A or B is the root node, then the root is the LCA and we just return the root, which is the end point of the recursion. As we keep divide the tree into sub-trees, eventually, we’ll hit either A and B.

To combine sub-problem solutions, if LCA(left tree) returns a node, we know that both A and B locate in left tree and the returned node is the final result. If both LCA(left) and LCA(right) return non-empty nodes, it means A and B are in left and right tree respectively. In this case, the root node is the lowest common node.

Check Lowest Common Ancestor for detailed analysis and solution.

Some of the solutions here assumes that there is reference to the root node, some assumes that tree is a BST. Sharing my solution using hashmap, without reference to root node and tree can be BST or non-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 } 
 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; } 

The code in Php. I’ve assumed the tree is an Array binary tree. Therefore, you don’t even require the tree to calculate the LCA. input: index of two nodes output: index of LCA

  < ?php global $Ps; function parents($l,$Ps) { if($l % 2 ==0) $p = ($l-2)/2; else $p = ($l-1)/2; array_push($Ps,$p); if($p !=0) parents($p,$Ps); return $Ps; } function lca($n,$m) { $LCA = 0; $arr1 = array(); $arr2 = array(); unset($Ps); $Ps = array_fill(0,1,0); $arr1 = parents($n,$arr1); unset($Ps); $Ps = array_fill(0,1,0); $arr2 = parents($m,$arr2); if(count($arr1) > count($arr2)) $limit = count($arr2); else $limit = count($arr1); for($i =0;$i< $limit;$i++) { if($arr1[$i] == $arr2[$i]) { $LCA = $arr1[$i]; break; } } return $LCA;//this is the index of the element in the tree } var_dump(lca(5,6)); ?> 

Do tell me if there are any shortcomings.