如何find任意二叉树中两个节点的最低共同祖先？

这里的二叉树可能不一定是二叉search树。
该结构可以被视为 –

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

我可以和朋友一起解决的最大的解决scheme就是这样的 –
考虑这个二叉树 ：

二叉树http://lcm.csa.iisc.ernet.in/dsa/img151.gif

中序遍历产生 – 8，4，9，2，5，1，6，3，7

而后序遍历产生 – 8,9,4,5,2,6,7,3,1

例如，如果我们想要find节点8和节点5的共同祖先，那么我们在中序树遍历中列出所有在8和5之间的节点，在这种情况下恰好是[4，9 ，2]。 然后我们检查这个列表中的哪个节点在后序遍历中最后出现，这是2.因此，对于8和5的共同祖先是2。

这个algorithm的复杂性，我相信是O（n）（O（n）对于inorder / postorder遍历，其余的步骤再次是O（n），因为它们只不过是数组中的简单迭代）。 但是这是错误的。 🙂

但是这是一个非常粗糙的方法，我不确定是否在某些情况下出现故障。 有没有其他（可能更优化）解决这个问题？

Answer 1

Nick Johnson是正确的，如果没有父指针，那么O（n）时间复杂度algorithm是最好的。）对于该algorithm的简单recursion版本，请参阅Kinding的post中的代码，该代码在O（n）时间。

但请记住，如果您的节点具有父指针，则可以使用改进的algorithm。 对于所讨论的两个节点，从节点开始构build一个包含从根节点到节点的path的列表，然后插入父节点。

所以对于你的例子中的8，你会得到（显示步骤）：{4}，{2,4}，{1，2，4}

对相关的其他节点执行相同操作，导致（步骤未显示）：{1，2}

现在比较一下你列出的两个列表，寻找列表不同的第一个元素，或者列表中的最后一个元素，以先到者为准。

这个algorithm需要O（h）时间，其中h是树的高度。 在最坏的情况下，O（h）等价于O（n），但是如果树是平衡的，那只有O（log（n））。 它也需要O（h）空间。 一个改进的版本是可能的，只使用恒定的空间，代码显示在CEGRD的post中

---

无论树是如何构build的，如果这将是一个操作，你在树上执行很多次而不改变它，还有其他的algorithm，你可以使用，需要O（n）[线性]准备时间，然后find任何对只需要O（1）[constant]时间。 有关这些algorithm的参考，请参阅维基百科上最低的共同祖先问题页面。 （信贷贾森最初发布此链接）

Answer 2

从root开始向下移动，如果发现有p或q作为其直接子节点的任何节点，那么它是LCA。 （编辑 – 这应该是如果p或q是节点的值，则返回它，否则当p或q中的一个是另一个的直接子节点时，它将失败。

否则，如果你find一个在右（或左）子树中有p的节点，并且在它的左（或右）子树中findq ，那么它就是LCA。

固定的代码如下所示：

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

当其中一个是直接的孩子时，下面的代码失败。

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

代码在行动

Answer 3

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

Answer 4

到目前为止给出的答案使用recursion或存储，例如，在内存中的path。

如果你有一个非常深的树，这两种方法可能会失败。

这是我的这个问题。 当我们检查两个节点的深度（距根的距离）时，如果它们相等，则可以安全地从两个节点向共同的祖先向上移动。 如果其中一个深度较大，那么我们应该从较深的节点向上移动，而另一个则停留在另一个节点。

这里是代码：

 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; 

该algorithm的时间复杂度为：O（n）。 该algorithm的空间复杂度为：O（1）。

关于深度的计算，我们可以先记住这个定义：如果v是root，depth（v）= 0; 否则，depth（v）= depth（parent（v））+1。我们可以计算深度如下：

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

Answer 5

那么，这种取决于你的二叉树的结构。 大概你有一些方法find所需的叶节点给定的树的根 – 只是适用于这两个值，直到你select的分支分歧。

如果你没有办法根据给定的根来find想要的叶子，那么你唯一的解决scheme – 无论是在正常的操作和find最后的公共节点 – 是对树的蛮力search。

Answer 6

这可以在： – 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; } } } 

Answer 7

Tarjan的离线最小公共祖先algorithm已经足够了（参见Wikipedia ）。 维基百科上有更多的问题（最常见的祖先问题）。

Answer 8

找出两个节点的共同祖先：

• 使用二进制search在树中查找给定节点Node1，并将所有在此进程中访问的节点保存在一个数组中，如A1所示。 时间 – O（logn），空间 – O（logn）
• 使用二进制search在树中find给定的节点2，并将在此过程中访问的所有节点保存在数组中，如A2。 时间 – O（logn），空间 – O（logn）
• 如果A1列表或A2列表是空的，那么一个节点不存在，所以没有共同的祖先。
• 如果A1列表和A2列表非空，那么查看列表直到find不匹配的节点。 只要你find这样一个节点，那么之前的节点是共同的祖先。

这将适用于二叉search树。

Answer 9

我已经尝试了Java中的说明图片和工作代码，

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

Answer 10

下面的recursionalgorithm将在O（log N）中运行一个平衡二叉树。 如果传入getLCA（）函数的节点中的任何一个与根相同，则根将是LCA，并且将不需要执行任何恢复。

testing用例。 [1]节点n1和n2都在树中，并驻留在其父节点的任一侧。 [2]节点n1或n2是根，LCA是根。 [3]只有n1或n2在树中，LCA将是树根的左子树的根节点，或者LCA将是树根的右子树的根节点。

[4] n1或n2在树中，没有LCA。 [5] n1和n2都是相邻的直线，LCA将是n1或n2，它们都是靠近树的根的。

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

Answer 11

只要从给定的两个节点（比如p和q中find祖先，都在同一个子树中（意味着它们的值都小于或者大于根大小），就从整棵树的root走下来。

这直接从根源走向最不起眼的祖先，而不是看着树的其余部分，所以它的速度非常快。 几种方法来做到这一点。

迭代，O（1）空间

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

如果溢出，我会做（root.val – （long）p.val）*（root.val – （long）q.val）

recursion

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

Answer 12

在scala中，代码是：

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

Answer 13

 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 } 

Answer 14

如果它是节点x的子节点为2 * x和2 * x + 1的完全二叉树，则比有更快的方法

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

它是如何工作的

1. 获取代表x和y使用二进制search的位是O（log（32））
2. x和y的二进制表示法的通用前缀是共同的祖先
3. 无论哪一个以较大的比特数表示由k >> diff带到相同的比特
4. k = x ^ y erazes x和y的通用前缀
5. find代表剩余后缀的位
6. 通过后缀位移位x或y得到公共前缀，这是共同的祖先。

这是有效的，因为基本上把这个较大的数字recursion地分成两个，直到两个数字相等为止。 这个数字是共同的祖先。 划分实际上是右移操作。 所以我们需要find两个数字的共同前缀来find最近的祖先

Answer 15

这是C ++的方式。 试图保持algorithm尽可能容易理解：

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

如何使用它：

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

Answer 16

find最低公共祖先最简单的方法是使用以下algorithm：

检查根节点

如果value1和value2严格小于根节点的值 
    检查左子树
否则，如果value1和value2严格大于根节点的值 
    检查右子树
其他
    返回根

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

Answer 17

我find了解决scheme

1. 取下
2. 以预购
3. 采取后置

根据3次遍历，您可以决定谁是LCA。 从LCAfind两个节点的距离。 添加这两个距离，这是答案。

Answer 18

考虑这棵树

如果我们做后序遍历，find第一个出现的共同前辈和后继者，我们得到共同的祖先。

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

• 例如：1

8,11最不共同的祖先

在后序中我们有=> 9,14,15,13,​​12,7 8和11之后我们有=> 7,3,1,0,2,6,4,5,12,9 8和11之前

9是第一个常用的数字，在后序8和11之后，在8和11之前，因此9是答案

• 例如：2

5,10最不共同的祖先

11,9,14,15,13,​​12,7预购7,3,1,0,2,6,4

7是5,10之后的第一个数字，5,10之前在前，因此7是答案

Answer 19

这是我的想法，

1. find第一个节点的路线，将其存储到arr1。
2. 开始查找2节点的路由，同时检查从根到arr1的每个值。
3. 价值不同的时候退出。 旧的匹配值是LCA。

复杂性：第1步：O（n），第2步= O（n），总= O（n）。

Answer 20

这里有两种方法在c＃（.net）（上面已经讨论过）中供参考：

1. 在二叉树中查找LCA的recursion版本（O（N） – 至多访问每个节点）（解决scheme的要点是LCA是（a）二叉树中仅两个元素位于子树的任一侧的节点（左（右）是LCA （b）也不pipe哪一个节点在哪一边 – 最初我试图保留这个信息，显然recursion函数变得如此混乱，一旦我意识到它，就变得非常优雅。

2. search两个节点（O（N）），并跟踪path（使用额外的空间 – 所以，＃1可能是优越的，即使认为如果二叉树平衡良好，那么空间可能可以忽略不计，因为额外的内存消耗只是在为O（log（N））。

   以便比较path（本质上与接受的答案类似），但path是通过假定指针节点不存在于二叉树节点中来计算的）

3. 为了完成（ 与问题无关 ），BST中的LCA（O（log（N））

4. testing

recursion：

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

上面的私有recursion版本通过以下公共方法调用：

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

通过跟踪两个节点的path解决scheme：

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

FindNodeAndPath被定义为

 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） – 无关（仅供参考）

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

unit testing

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

Answer 21

如果有人对伪代码感兴趣，那么这里就是一个。

 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 

Answer 22

虽然这已经被回答了，但这是我用C编程语言来解决这个问题的方法。 尽pipe代码显示了二叉search树（就insert（）而言），但该algorithm也适用于二叉树。 其思想是遍历从节点A到节点B的所有节点，在遍历中查找这些节点的索引。 遍历顺序最大的节点是最低的共同祖先。

这是一个工作的C代码来实现一个函数来查找二叉树中最低的共同祖先。 我也提供所有的实用function等，但跳到CommonAncestor（）快速了解。

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

Answer 23

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

Answer 24

Try like this

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

Answer 25

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.

码：

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

Answer 26

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

Answer 27

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.

Answer 28

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 } 

Answer 29

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.

Answer 30

//If both the values are less than the current node then traverse the left subtree //Or If both the values are greater than the current node then traverse the right subtree //Or LCA is the current node

 public BSTNode findLowestCommonAncestor(BSTNode currentRoot, int a, int b){ BSTNode commonAncestor = null; if (currentRoot == null) { System.out.println("The Tree does not exist"); return null; } int currentNodeValue = currentRoot.getValue(); //If both the values are less than the current node then traverse the left subtree //Or If both the values are greater than the current node then traverse the right subtree //Or LCA is the current node if (a < currentNodeValue && b < currentNodeValue) { commonAncestor = findLowestCommonAncestor(currentRoot.getLeft(), a, b); } else if (a > currentNodeValue && b > currentNodeValue) { commonAncestor = findLowestCommonAncestor(currentRoot.getRight(), a, b); } else { commonAncestor = currentRoot; } return commonAncestor; }