Comment trouver l’ancêtre commun le plus bas de deux nœuds dans un arbre binary?

Nick Johnson a raison de dire que l’algorithme de complexité temporelle O (n) est le meilleur que l’on puisse faire si vous n’avez pas de pointeurs parents.) Pour une version récursive simple de cet algorithme, voyez le code de Kinding .

Mais gardez à l’esprit que si vos nœuds ont des pointeurs parents, un algorithme amélioré est possible. Pour les deux nœuds en question, construisez une liste contenant le chemin d’access de la racine au nœud en commençant par le nœud et en insérant le parent par l’avant.

Donc pour 8 dans votre exemple, vous obtenez (montrant les étapes): {4}, {2, 4}, {1, 2, 4}

Faites la même chose pour votre autre noeud en question, ce qui entraîne (étapes non affichées): {1, 2}

Comparez maintenant les deux listes que vous avez faites en recherchant le premier élément où la liste diffère ou le dernier élément de l’une des listes, selon la première éventualité.

Cet algorithme nécessite O (h) temps où h est la hauteur de l’arbre. Dans le pire des cas, O (h) est équivalent à O (n), mais si l’arbre est équilibré, c’est seulement O (log (n)). Il nécessite également un espace O (h). Une version améliorée est possible qui utilise uniquement un espace constant, avec le code affiché dans la publication du CEGRD

Indépendamment de la manière dont l’arbre est construit, s’il s’agit d’une opération que vous effectuez plusieurs fois sur l’arborescence sans la modifier entre les deux, vous pouvez utiliser d’autres algorithmes qui nécessitent une préparation du temps O (n) [linéaire], la paire ne prend que le temps O (1) [constant]. Pour des références à ces algorithmes, reportez-vous à la page sur les problèmes d’ancêtres communs les plus bas sur Wikipedia . (Crédit à Jason pour avoir posté ce lien)

En partant du nœud root et en descendant si vous trouvez un nœud ayant p ou q comme enfant direct, alors c’est l’ACV. (edit – cela devrait être si p ou q est la valeur du nœud, retournez-le. Sinon, il échouera si l’un des p ou q est un enfant direct de l’autre.)

Sinon, si vous trouvez un nœud avec p dans son sous-arbre droit (ou gauche) et q dans son sous-arbre gauche (ou droit), alors c’est l’ACV.

Le code fixe ressemble à:

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

Le code ci-dessous échoue lorsque l’un ou l’autre est l’enfant direct de l’autre.

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

Code en action

Voici le code de travail dans 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; } 

Les réponses données jusqu’à présent utilisent la récursivité ou stockent, par exemple, un chemin en mémoire.

Ces deux approches peuvent échouer si vous avez un arbre très profond.

Voici ma réponse à cette question. Lorsque nous vérifions la profondeur (distance de la racine) des deux nœuds, s’ils sont égaux, nous pouvons nous déplacer en toute sécurité des deux nœuds vers l’ancêtre commun. Si l’une des profondeurs est plus grande, nous devrions monter du nœud plus profond tout en restant dans l’autre.

Voici le code:

 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 complexité temporelle de cet algorithme est la suivante: O (n). La complexité d’espace de cet algorithme est la suivante: O (1).

En ce qui concerne le calcul de la profondeur, nous pouvons d’abord nous souvenir de la définition: Si v est root, depth (v) = 0; Sinon, depth (v) = depth (parent (v)) + 1. On peut calculer la profondeur comme suit:

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

Eh bien, cela dépend de la structure de votre arbre binary. Vous avez probablement un moyen de trouver le nœud feuille désiré à la racine de l’arbre – appliquez simplement cela aux deux valeurs jusqu’à ce que les twigs que vous choisissez divergent.

Si vous n’avez pas le moyen de trouver la feuille désirée à la racine, votre seule solution – à la fois en fonctionnement normal et pour trouver le dernier nœud commun – est une recherche en force de l’arborescence.

Cela peut être trouvé à: – 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; } } } 

L’algorithme des ancêtres les moins communs hors ligne de Tarjan est assez bon (voir aussi Wikipedia ). Il y a plus sur le problème (le problème d’ancêtre commun le plus bas) sur Wikipedia .

Pour trouver un ancêtre commun de deux nœuds: –

• Recherchez le nœud donné Node1 dans l’arborescence en utilisant la recherche binary et enregistrez tous les nœuds visités dans ce processus dans un tableau, par exemple A1. Time – O (logn), Espace – O (logn)
• Trouvez le Node2 donné dans l’arborescence en utilisant la recherche binary et enregistrez tous les nœuds visités dans ce processus dans un tableau, disons A2. Time – O (logn), Espace – O (logn)
• Si la liste A1 ou la liste A2 est vide, alors le nœud n’existe pas, il n’y a donc pas d’ancêtre commun.
• Si la liste A1 et la liste A2 ne sont pas vides, regardez dans la liste jusqu’à ce que vous trouviez un nœud sans correspondance. Dès que vous trouvez un tel nœud, alors le nœud précédent est un ancêtre commun.

Cela fonctionnerait pour l’arbre de recherche binary.

J’ai fait une tentative avec des illustrations et du code de travail en Java,

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

L’algorithme récursif ci-dessous sera exécuté dans O (log N) pour un arbre binary équilibré. Si l’un des noeuds passés dans la fonction getLCA () est identique à la racine, la racine sera l’ACV et il ne sera plus nécessaire d’effectuer de recussrion.

Cas de test [1] Les deux nœuds n1 & n2 sont dans l’arborescence et résident de chaque côté de leur nœud parent. [2] Soit le noeud n1 ou n2 est la racine, l’ACV est la racine. [3] Seuls n1 ou n2 sont dans l’arborescence, LCA sera soit le nœud racine du sous-arbre gauche de la racine de l’arbre, soit le LCA sera le nœud racine du sous-arbre droit de la racine de l’arborescence.

[4] Ni n1 ni n2 ne sont dans l’arbre, il n’y a pas de LCA. [5] n1 et n2 sont tous deux en ligne droite les uns à côté des autres, l’ACV sera soit de n1 soit de n2 qui se ferme à la racine de l’arbre.

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

Il suffit de descendre de la root l’arbre entier tant que les deux nœuds donnés, p et q , pour lesquels Ancestor doit être trouvé, sont dans le même sous-arbre (ce qui signifie que leurs valeurs sont plus petites ou plus grandes que celles de root).

Cela va directement de la racine au plus petit ancêtre commun, sans regarder le rest de l’arbre, donc c’est à peu près aussi rapide que possible. Quelques façons de le faire

Itératif, O (1) espace

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

en cas de débordement, je le ferais (root.val - (long) p.val) * (root.val - (long) q.val)

Récursive

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

En scala, le code est:

 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 } 

S’il s’agit d’un arbre binary complet avec des enfants du noeud x en 2 * x et 2 * x + 1, il existe un moyen plus rapide de le faire

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

Comment ça marche

1. obtenir les bits nécessaires pour représenter x & y qui en utilisant la recherche binary est O (log (32))
2. le préfixe commun de la notation binary de x & y est l’ancêtre commun
3. selon le plus grand nombre de bits est amené au même bit par k >> diff
4. k = x ^ y efface le préfixe commun de x & y
5. trouver des bits représentant le suffixe restant
6. décaler x ou y par suffixe bits pour obtenir le préfixe commun qui est l’ancêtre commun.

Cela fonctionne parce que fondamentalement diviser le plus grand nombre par deux récursivement jusqu’à ce que les deux nombres soient égaux. Ce nombre est l’ancêtre commun. La division est en fait l’opearation du bon décalage. Il faut donc trouver le préfixe commun de deux nombres pour trouver l’ancêtre le plus proche

Voici la façon de le faire en C ++. Ont essayé de garder l’algorithme aussi facile que possible pour comprendre:

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

Comment l’utiliser:

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

La méthode la plus simple pour trouver l’ancêtre commun le plus bas consiste à utiliser l’algorithme suivant:

 Examiner le nœud racine

 si valeur1 et valeur2 sont ssortingctement inférieures à la valeur du nœud racine 
     Examinez le sous-arbre de gauche
 sinon si value1 et value2 sont ssortingctement supérieurs à la valeur du nœud racine 
     Examinez le sous-arbre droit
 autre
     retourne la racine

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

J’ai trouvé une solution

1. Prendre commande
2. Prendre la précommande
3. Prendre un envoi postal

Selon 3 parcours, vous pouvez décider qui est l’ACV. De LCA trouver la distance des deux nœuds. Ajoutez ces deux distances, qui est la réponse.

Considérez cet arbre

Si nous effectuons des traversées de post-ordre et de précommande et que nous trouvons le premier prédécesseur et successeur commun, nous obtenons l’ancêtre commun.

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

• par exemple: 1

Ancêtre le moins commun de 8,11

en post-traitement nous avons => 9,14,15,13,12,7 après 8 et 11 en précommande nous avons => 7,3,1,0,2,6,4,5,12,9 avant 8 et 11

9 est le premier nombre commun qui se produit après 8 et 11 en post-commande et avant 8 et 11 en pré-commande, donc 9 est la réponse

• par exemple: 2

Moins ancêtre commun de 5,10

11,9,14,15,13,12,7 en post-commande 7,3,1,0,2,6,4 en pré-commande

7 est le premier nombre qui se produit après 5,10 en post-commande et avant 5,10 en pré-commande, donc 7 est la réponse

Voici ce que je pense,

1. Trouvez l’itinéraire pour le premier nœud, stockez-le sur arr1.
2. Commencez par trouver la route pour le nœud 2, tout en vérifiant chaque valeur de root à arr1.
3. heure lorsque la valeur diffère, quittez. L’ancienne valeur correspondante est l’ACV.

Complexité: étape 1: O (n), étape 2 = ~ O (n), total = ~ O (n).

Voici deux approches dans c # (.net) (toutes deux discutées ci-dessus) pour référence:

1. Version récursive de la recherche de LCA dans un arbre binary (O (N) – comme au maximum chaque nœud est visité) et à droite) LCA. (b) Et quel que soit le nœud qui est présent de chaque côté – au début, j’ai essayé de garder cette information, et évidemment la fonction récursive devient si confuse.

2. Recherche des deux nœuds (O (N)) et suivi des chemins (utilise un espace supplémentaire – donc, # 1 est probablement supérieur même si l’espace est probablement négligeable si l’arbre binary est bien équilibré) O (log (N)).

   de sorte que les chemins soient comparés (essentiellement similaires à la réponse acceptée – mais les chemins sont calculés en supposant que le nœud de pointeur n’est pas présent dans le nœud d’arbre binary)

3. Juste pour l’achèvement ( non lié à la question ), ACV en BST (O (log (N))

4. Des tests

Récursive:

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

où la version récursive privée ci-dessus est appelée par la méthode publique suivante:

 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(ssortingng.Format("Least common ancenstor not found for the given elements: {0},{1}", e1, e2)); } return node; } 

Solution en gardant une trace des chemins des deux nœuds:

 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(ssortingng.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(ssortingng.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; } 

où FindNodeAndPath est défini comme

 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) - non lié (juste pour compléter pour référence)

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

Tests unitaires

 [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 quelqu’un qui s’intéresse au pseudo-code (pour les travaux universitaires à domicile) en est un.

 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 

Même si cela a déjà été répondu, c’est mon approche de ce problème en utilisant le langage de programmation C. Bien que le code montre un arbre de recherche binary (en ce qui concerne insert ()), mais l’algorithme fonctionne également pour un arbre binary. L’idée est de passer en revue tous les noeuds situés entre le noeud A et le noeud B, en recherchant les index dans la traversée post-ordre. Le noeud avec index maximal dans la traversée de post-ordre est l’ancêtre commun le plus bas.

Ceci est un code C fonctionnel pour implémenter une fonction permettant de trouver l’ancêtre commun le plus bas dans un arbre binary. Je fournis également toutes les fonctions utilitaires, mais passez à CommonAncestor () pour une compréhension rapide.

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

Essayez comme ça

 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.

Code:

 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

   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.