How to find the lowest common ancestor of two nodes in any binary tree

Question

The Binary Tree here is may not necessarily be a Binary Search Tree  The structure could be taken as -  struct node       int data      struct node  left      struct node  right       The maximum solution I could work out with a friend was something of this sort - Consider this binary tree      The inorder traversal yields - 8  4  9  2  5  1  6  3  7  And the postorder traversal yields - 8  9  4  5  2  6  7  3  1  So for instance  if we want to find the common ancestor of nodes 8 and 5  then we make a list of all the nodes which are between 8 and 5 in the inorder tree traversal  which in this case happens to be  4  9  2   Then we check which node in this list appears last in the postorder traversal  which is 2  Hence the common ancestor for 8 and 5 is 2   The complexity for this algorithm  I believe is O n   O n  for inorder postorder traversals  the rest of the steps again being O n  since they are nothing more than simple iterations in arrays   But there is a strong chance that this is wrong   -   But this is a very crude approach  and I m not sure if it breaks down for some case  Is there any other  possibly more optimal  solution to this problem

User · Answer

public class LeastCommonAncestor        private TreeNode root       private static class TreeNode           TreeNode left          TreeNode right          int item           TreeNode  TreeNode left  TreeNode right  int item                this left   left              this right   right              this item   item                       public void createBinaryTree  Integer   arr            if  arr    null                 throw new NullPointerException  The input array is null                        root   new TreeNode null  null  arr 0             final Queue lt TreeNode gt  queue   new LinkedList lt TreeNode gt             queue add root            final int half   arr length   2           for  int i   0  i  lt  half  i                  if  arr i     null                    final TreeNode current   queue poll                    final int left   2   i   1                  final int right   2   i   2                   if  arr left     null                        current left   new TreeNode null  null  arr left                        queue add current left                                     if  right  lt  arr length  amp  amp  arr right     null                        current right   new TreeNode null  null  arr right                        queue add current right                                                        private static class LCAData           TreeNode lca          int count           public LCAData TreeNode parent  int count                this lca   parent              this count   count                        public int leastCommonAncestor int n1  int n2            if  root    null                throw new NoSuchElementException  The tree is empty                        LCAData lcaData   new LCAData null  0             foundMatch  root  lcaData  n1   n2                           QQ  boolean was returned but never used by caller                      foundMatchAndDuplicate  root  lcaData  n1   n2  new HashSet lt Integer gt               if  lcaData lca    null                return lcaData lca item            else                                  QQ  Illegal thrown after processing function                              throw new IllegalArgumentException  The tree does not contain either one or more of input data                                          Duplicate n1  n1         Duplicate in Tree               x                           x                 gt  succeeds               x                           1                 gt  fails                1                           x                 gt  succeeds by throwing exception               1                           1                 gt  succeeds                 private boolean foundMatch  TreeNode node  LCAData lcaData  int n1  int n2              if  node    null                  return false                           if  lcaData count    2                  return false                           if   node item    n1    node item    n2   amp  amp  lcaData count    1                  lcaData count                  return true                           boolean foundInCurrent   false            if  node item    n1    node item    n2                  lcaData count                  foundInCurrent   true                           boolean foundInLeft   foundMatch node left  lcaData  n1  n2             boolean foundInRight   foundMatch node right  lcaData  n1  n2                if   foundInLeft  amp  amp  foundInRight      foundInCurrent  amp  amp  foundInRight      foundInCurrent  amp  amp  foundInLeft                   lcaData lca   node                return true                         return foundInCurrent     foundInLeft    foundInRight                 private boolean foundMatchAndDuplicate  TreeNode node  LCAData lcaData  int n1  int n2  Set lt Integer gt  set            if  node    null                return false                        when both were found         if  lcaData count    2                return false                        when only one of them is found         if   node item    n1    node item    n2   amp  amp  lcaData count    1                if   set contains node item                     lcaData count                    return true                                   boolean foundInCurrent   false               when nothing was found  count    0   or a duplicate was found  count    1          if  node item    n1    node item    n2                if   set contains node item                     set add node item                   lcaData count                              foundInCurrent   true                     boolean foundInLeft   foundMatchAndDuplicate node left  lcaData  n1  n2  set           boolean foundInRight   foundMatchAndDuplicate node right  lcaData  n1  n2  set            if    foundInLeft  amp  amp  foundInRight                       foundInCurrent  amp  amp  foundInRight                           foundInCurrent  amp  amp  foundInLeft    amp  amp                          lcaData lca    null                lcaData lca   node              return true                     return foundInCurrent     foundInLeft    foundInRight                 public static void main String args                             Binary tree with unique values                      Integer   arr1    1  2  3  4  null  6  7  8  null  null  null  null  9           LeastCommonAncestor commonAncestor   new LeastCommonAncestor            commonAncestor createBinaryTree arr1            int ancestor   commonAncestor leastCommonAncestor 2  4           System out println  Expected 2  actual     ancestor            ancestor   commonAncestor leastCommonAncestor 2  7           System out println  Expected 1  actual    ancestor            ancestor   commonAncestor leastCommonAncestor 2  6           System out println  Expected 1  actual     ancestor            ancestor   commonAncestor leastCommonAncestor 2  1           System out println  Expected 1  actual    ancestor            ancestor   commonAncestor leastCommonAncestor 3  8           System out println  Expected 1  actual    ancestor            ancestor   commonAncestor leastCommonAncestor 7  9           System out println  Expected 3  actual    ancestor               duplicate request          try               ancestor   commonAncestor leastCommonAncestor 7  7             catch  Exception e                System out println  expected exception                                      Binary tree with duplicate values                      Integer   arr2    1  2  8  4  null  6  7  8  null  null  null  null  9           commonAncestor   new LeastCommonAncestor            commonAncestor createBinaryTree arr2               duplicate requested         ancestor   commonAncestor leastCommonAncestor 8  8           System out println  Expected 1  actual     ancestor            ancestor   commonAncestor leastCommonAncestor 4  8           System out println  Expected 4  actual    ancestor            ancestor   commonAncestor leastCommonAncestor 7  8           System out println  Expected 8  actual    ancestor            ancestor   commonAncestor leastCommonAncestor 2  6           System out println  Expected 1  actual     ancestor             ancestor   commonAncestor leastCommonAncestor 8  9             System out println  Expected 8  actual    ancestor      failed

User · Answer

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

User · Answer

Nick Johnson is correct that a an O n  time complexity algorithm is the best you can do if you have no parent pointers   For a simple recursive version of that algorithm see the code in Kinding s post which runs in O n  time   But keep in mind that if your nodes have parent pointers  an improved algorithm is possible  For both nodes in question construct a list containing the path from root to the node by starting at the node  and front inserting the parent   So for 8 in your example  you get  showing steps    4    2  4    1   2  4   Do the same for your other node in question  resulting in  steps not shown    1  2   Now compare the two lists you made looking for the first element where the list differ  or the last element of one of the lists  whichever comes first   This algorithm requires O h  time where h is the height of the tree  In the worst case O h  is equivalent to O n   but if the tree is balanced  that is only O log n    It also requires O h  space  An improved version is possible that uses only constant space  with code shown in CEGRD s post    Regardless of how the tree is constructed  if this will be an operation you perform many times on the tree without changing it in between  there are other algorithms you can use that require O n   linear  time preparation  but then finding any pair takes only O 1   constant  time  For references to these algorithms  see the the lowest common ancestor problem page on Wikipedia   Credit to Jason for originally posting this link

User · Answer

The answers given so far uses recursion or stores  for instance  a path in memory   Both of these approaches might fail if you have a very deep tree   Here is my take on this question  When we check the depth  distance from the root  of both nodes  if they are equal  then we can safely move upward from both nodes towards the common ancestor  If one of the depth is bigger then we should move upward from the deeper node while staying in the other one   Here is the code   findLowestCommonAncestor v w     depth vv   depth v     depth ww   depth w      vv   v     ww   w     while  depth vv    depth ww         if   depth vv  gt  depth ww           vv   parent vv         depth vv--      else         ww   parent ww         depth ww--               while  vv    ww         vv   parent vv       ww   parent ww          return vv        The time complexity of this algorithm is  O n   The space complexity of this algorithm is  O 1    Regarding the computation of the depth  we can first remember the definition  If v is root  depth v    0  Otherwise  depth v    depth parent v     1  We can compute depth as follows   depth v     int d   0    vv   v    while   vv is not root         vv   parent vv       d          return d

User · Answer

If someone interested in pseudo code for university home works  here is one   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

User · Answer

Here is the C   way of doing it  Have tried to keep the algorithm as much easy as possible to understand      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- gt getData      m Node1       found     pNode- gt getData      m Node2        found    Search pNode- gt getLeft        below condition can be after this as well     found    Search pNode- gt getRight          if found    TOTAL NODES  amp  amp  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           How to use it   LowestCommonAncestor lca  BinaryNode t  pNode   lca Search pWhateverBinaryTreeNodeToBeginWith   if pNode    0

User · Answer

Here is the working code in 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  amp  amp  right    null          return root           return  left    null    left   right

User · Answer

Here are two approaches in c    net   both discussed above  for reference   Recursive version of finding LCA in binary tree  O N  - as at most each node is visited   main points of the solution is LCA is  a  only node in binary tree where both elements reside either side of the subtrees  left and right  is LCA   b  And also it doesn t matter which node is present either side - initially i tried to keep that info  and obviously the recursive function become so confusing  once i realized it  it became very elegant   Searching both nodes  O N    and keeping track of paths  uses extra space - so   1 is probably superior even thought the space is probably negligible if the binary tree is well balanced as then extra memory consumption will be just in O log N    so that the paths are compared  essentailly similar to accepted answer - but the paths is calculated by assuming pointer node is not present in the binary tree node   Just for the completion  not related to question   LCA in BST  O log N    Tests   Recursive  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  amp  amp  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             where above private recursive version is invoked by following public method  public BinaryTreeNode LeastCommonAncestorUsingRecursion int e1  int e2                        var n   this FindNode this  root  e1               if null    n                                throw new Exception  quot Element not found   quot    e1                             if  e1    e2                                   return n                            n   this FindNode this  root  e2               if  null    n                                throw new Exception  quot Element not found   quot    e2                             var node   this LeastCommonAncestorUsingRecursion this  root  e1  e2               if  null    node                                throw new Exception string Format  quot Least common ancenstor not found for the given elements   0   1  quot   e1  e2                              return node             Solution by keeping track of paths of both nodes  public BinaryTreeNode LeastCommonAncestorUsingPaths int e1  int e2                        var path1   new List lt BinaryTreeNode gt                 var node1   this FindNodeAndPath this  root  e1  path1               if node1    null                                throw new Exception string Format  quot Element  0  is not found quot   e1                              if e1    e2                                return node1                            List lt BinaryTreeNode gt  path2   new List lt BinaryTreeNode gt                 var node2   this FindNodeAndPath this  root  e2  path2               if  node1    null                                throw new Exception string Format  quot Element  0  is not found quot   e2                              BinaryTreeNode lca   null              Debug Assert path1 0     this  root               Debug Assert path2 0     this  root               int i   0              while  i  lt  path1 Count                   amp  amp   i  lt  path2 Count                   amp  amp   path2 i     path1 i                                  lca   path1 i                   i                              Debug Assert null    lca               return lca             where FindNodeAndPath is defined as private BinaryTreeNode FindNodeAndPath BinaryTreeNode node  int e  List lt BinaryTreeNode gt  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  - not related  just for completion for reference  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  gt  e1    amp  amp   iterativeNode Element  gt  e2                                         iterativeNode   iterativeNode Left                                    else if  iterativeNode Element  lt  e1   amp  amp   iterativeNode Element  lt  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             Unit Tests  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  lt  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

User · Answer

Consider this tree    If we do postorder and preorder traversal and find the first occuring common predecessor and successor  we get the common ancestor   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   eg  1   Least common ancestor of 8 11  in postorder we have    9 14 15 13 12 7 after 8  amp  11 in preorder we have   7 3 1 0 2 6 4 5 12 9 before 8  amp  11  9 is the first common number that occurs after 8 amp  11 in postorder and before 8  amp  11 in preorder  hence 9 is the answer   eg  2   Least common ancestor of 5 10  11 9 14 15 13 12 7 in postorder 7 3 1 0 2 6 4 in preorder  7 is the first number that occurs after 5 10 in postorder and before 5 10 in preorder  hence 7 is the answer

User · Answer

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  lt  currentNodeValue  amp  amp  b  lt  currentNodeValue            commonAncestor   findLowestCommonAncestor currentRoot getLeft    a  b         else if  a  gt  currentNodeValue  amp  amp  b  gt  currentNodeValue            commonAncestor   findLowestCommonAncestor currentRoot getRight    a  b         else           commonAncestor   currentRoot             return commonAncestor

User · Answer

This can be found at - 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- gt left  p    root- gt left  q    root- gt right   p    root- gt right   q                return root            else               l LowestCommonAncestor root- gt left   p   q           r LowestCommonAncestor root- gt right   p  q            if l  NULL  amp  amp  r  NULL                        return root                    else                   temp    l  NULL  l r          return temp

User · Answer

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  i e  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- gt left  n1  n2   amp left set         if  leftCA             return leftCA                  if   right set          rightCA  findCA root- gt right  n1  n2   amp right set         if rightCA             return rightCA                   if  left set  amp  amp  right set          return root       else          set    left set    right set         return NULL

User · Answer

Try like this  node   lca node   root  int v1 int v2     if  root                return NULL            if root- gt data    v1    root- gt data    v2            return root       else               if  v1  gt  root- gt data  amp  amp  v2  lt  root- gt data      v1  lt  root- gt data  amp  amp  v2  gt  root- gt data                         return root                     if v1  lt  root- gt data  amp  amp  v2  lt  root- gt data                        root   lca root- gt left  v1  v2                      if v1  gt  root- gt data  amp  amp  v2  gt  root- gt data                        root   lca root- gt right  v1  v2                   return root

User · Answer

To find out common ancestor of two node  -    Find the given node Node1 in the tree using binary search and save all nodes visited in this process in an array say A1  Time - O logn   Space - O logn  Find the given Node2 in the tree using binary search and save all nodes visited in this process in an array say A2  Time - O logn   Space - O logn  If A1 list or A2 list is empty then one the node does not exist so there is no common ancestor  If A1 list and A2 list are non-empty then look into the list until you find non-matching node  As soon as you find such a node then node prior to that is common ancestor    This would work for binary search tree

User · Answer

The following is the fastest way to solve this   Space complexity O 1    Time complexity O n   If      If a node has both left and right value as not null  then that node is   your answer 3rd  if  from top   While iterating if a value is found  as   all the values are uniques and must be present  we don t need to   search its descendants  so just return the found node that matched  if   a node s both left and right branch contents null propagate null   upwards  when reached top-level recursion  if one branch returned   value  others do not keep propagating that value  when both returned   not null return current node  If it reaches root level recursion with   one null and another not null  return not null value  as the question    promises the value exists  it must be in the children tree of the   found node which we never traversed    class Solution       public TreeNode lowestCommonAncestor TreeNode root  TreeNode p  TreeNode q            if root    null  return null          if root val    p val    root val    q val  return root          TreeNode left   lowestCommonAncestor root left  p  q           TreeNode right   lowestCommonAncestor root right  p  q           if  left    null  amp  amp  right   null  return root          if  left    null  amp  amp  right   null  return null          return  left    null   left   right

User · Answer

Although this has been answered already  this is my approach to this problem using C programming language  Although the code shows a binary search tree  as far as insert   is concerned   but the algorithm works for a binary tree as well  The idea is to go over all nodes that lie from node A to node B in inorder traversal  lookup the indices for these in the post order traversal  The node with maximum index in post order traversal is the lowest common ancestor    This is a working C code to implement a function to find the lowest common ancestor in a binary tree  I am providing all the utility functions etc  as well  but jump to CommonAncestor   for quick understanding     include  lt stdio h gt   include  lt malloc h gt   include  lt stdlib h gt   include  lt math h gt   static inline int min  int a  int b        return   a  lt  b    a   b     static inline int max  int a  int b        return   a  gt  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- gt left   temp node- gt right   NULL      temp node- gt value   value      return temp node     node   insert node   root  int value        if   root            return createNode value              if  root- gt value  gt  value            root- gt left   insert root- gt left  value         else           root- gt right   insert root- gt 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- gt left  IN       IN i    root- gt value      i        inorder root- gt 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- gt left  POST       postorder root- gt right  POST       POST i    root- gt value      i        int findIndex int   A  int value        int i   0      for i   0  i lt  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 lt   max in val1  in val2   i              for j   0  j  lt  MAX  j                  if  IN ORDER i     POST ORDER j                     if  j  gt  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

User · Answer

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

User · Answer

Node  LCA Node  root  Node  p  Node  q      if   root  return NULL    if  root    p    root    q  return root    Node  L   LCA root- gt left  p  q     Node  R   LCA root- gt right  p  q     if  L  amp  amp  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 amp R subtrees

User · Answer

Starting from root node and moving downwards if you find any node that has either p or q as its direct child then it is the LCA   edit - this should be if p or q is the node s value  return it  Otherwise it will fail when one of p or q is a direct child of the other    Else if you find a node with p in its right or left  subtree and q in its left or right  subtree then it is the LCA   The fixed code looks like   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- gt left   p   q                       get LCA of p and q in right subtree                  treeNodePtr r findLCA root- gt right   p  q                       if one of p or q is in leftsubtree and other is in right                    then root it the LCA                  if l  amp  amp  r                            return root                                       else if l is not null  l is LCA                  else if l                            return l                    else                           return r                                  The below code fails when either is the direct child of other   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- gt left  p    root- gt left  q                root- gt right   p    root- gt right   q                    return root            else                      get LCA of p and q in left subtree                  treeNodePtr l findLCA root- gt left   p   q                       get LCA of p and q in right subtree                  treeNodePtr r findLCA root- gt right   p  q                       if one of p or q is in leftsubtree and other is in right                    then root it the LCA                  if l  amp  amp  r                            return root                                       else if l is not null  l is LCA                  else if l                            return l                    else                           return r                                  Code In Action

User · Answer

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       lt  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   gt  count  arr2            limit   count  arr2       else          limit   count  arr1        for  i  0  i lt  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      gt    Do tell me if there are any shortcomings

User · Answer

The easiest way to find the Lowest Common Ancestor is using the following algorithm    Examine root node  if value1 and value2 are strictly less that the value at the root node      Examine left subtree else if value1 and value2 are strictly greater that the value at the root node      Examine right subtree else     return root   public int LCA TreeNode root  int value 1  int value 2        while  root    null           if  value1  lt  root data  amp  amp  value2  lt  root data             return LCA root left  value1  value2          else if  value2  gt  root data  amp  amp  value2 2 root data             return LCA root right  value1  value2          else            return root            return null

User · Answer

Tarjan s off-line least common ancestors algorithm is good enough  cf  also Wikipedia   There is more on the problem  the lowest common ancestor problem  on Wikipedia

User · Answer

Just walk down from the whole tree s root as long as both given nodes  say p and q  for which Ancestor has to be found  are in the same sub-tree  meaning their values are both smaller or both larger than root s   This walks straight from the root to the Least Common Ancestor   not looking at the rest of the tree  so it s pretty much as fast as it gets  A few ways to do it   Iterative  O 1  space  Python   def lowestCommonAncestor self  root  p  q       while  root val - p val     root val - q val   gt  0          root    root left  root right  p val  gt  root val      return root    Java   public TreeNode lowestCommonAncestor TreeNode root  TreeNode p  TreeNode q        while   root val - p val     root val - q val   gt  0          root   p val  lt  root val   root left   root right      return root     in case of overflow  I d do  root val -  long p val     root val -  long q val   Recursive  Python   def lowestCommonAncestor self  root  p  q       next   p val  lt  root val  gt  q val and root left or              p val  gt  root val  lt  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   lt  1   root              lowestCommonAncestor p val  lt  root val   root left   root right  p  q

User · Answer

Solution 1  Recursive - Faster   The idea is to traverse the tree starting from root  If any of the given keys p and q matches with root  then root is LCA  assuming that both keys are present  If root doesn   t match with any of the keys  we recurse for left and right subtree   The node which has one key present in its left subtree and the other key present in right subtree is the LCA  If both keys lie in left subtree  then left subtree has LCA also  otherwise LCA lies in right subtree          Time Complexity  O n    Space Complexity  O h  - for recursive call stack      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  amp  amp  right    null            Solution 2  Iterative - Using parent pointers - Slower   Create an empty hash table  Insert p and all of its ancestors in hash table  Check if q or any of its ancestors exist in hash table  if yes then return the first existing ancestor          Time Complexity  O n  - In the worst case we might be visiting all the nodes of binary tree    Space Complexity  O n  - Space utilized the parent pointer Hash-table  ancestor set and queue  would be O n  each       class Solution       public TreeNode lowestCommonAncestor TreeNode root  TreeNode p  TreeNode q                HashMap lt TreeNode  TreeNode gt  parent map   new HashMap lt  gt             HashSet lt TreeNode gt  ancestors set   new HashSet lt  gt             Queue lt TreeNode gt  queue   new LinkedList lt  gt              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

User · Answer

In scala  you can     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    gt            if ab  a    ab   b  tree else             val temp   lca l a b             val temp2   lca r a b             if temp  null  amp  amp  temp2   null              tree           else if  temp  null  amp  amp  temp2  null              null           else if  temp  null  r else l                          case Leaf ab    gt  if ab  a    ab   b  tree else null

User · Answer

Well  this kind of depends how your Binary Tree is structured  Presumably you have some way of finding the desired leaf node given the root of the tree - simply apply that to both values until the branches you choose diverge   If you don t have a way to find the desired leaf given the root  then your only solution - both in normal operation and to find the last common node - is a brute-force search of the tree

User · Answer

Here is what I think    Find the route for the fist node   store it on to arr1  Start finding the route for the 2 node   while doing so check every value from root to arr1  time when value differs   exit  Old matched value is the LCA    Complexity   step 1   O n    step 2    O n    total    O n

User · Answer

I have made an attempt with illustrative pictures and working code in Java   http   tech bragboy com 2010 02 least-common-ancestor-without-using html

User · Answer

I found a solution   Take inorder Take preorder Take postorder   Depending on 3 traversals  you can decide who is the LCA  From LCA find distance of both nodes  Add these two distances  which is the answer

User · Answer

The below recursive algorithm will run in O log N  for a balanced binary tree  If either of the nodes passed into the getLCA   function are the same as the root then the root will be the LCA and there will be no need to perform any recussrion   Test cases    1  Both nodes n1  amp  n2 are in the tree and reside on either side of their parent node   2  Either node n1 or n2 is the root  the LCA is the root   3  Only n1 or n2 is in the tree  LCA will be either the root node of the left subtree of the tree root  or the LCA will be the root node of the right subtree of the tree root    4  Neither n1 or n2 is in the tree  there is no LCA   5  Both n1 and n2 are in a straight line next to each other  LCA will be either of n1 or n2 which ever is closes to the root of the tree     find the search node below root bool findNode node  root  node  search          base case     if root    NULL          return false       if root- gt val    search- gt val          return true         search for the node in the left and right subtrees  if found in either return true     return  findNode root- gt left  search     findNode root- gt right  search         returns the LCA  n1  amp  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- gt left  n1       bool n2OnLeft   findNode root- gt left  n2          n1  amp  n2 are on different sides of the root  so root is the LCA     if n1OnLeft    n2OnLeft          return root         if both n1  amp  n2 are on the left of the root traverse left sub tree only       to find the node where n1  amp  n2 diverge otherwise traverse right subtree     if n1OnLeft          return getLCA root- gt left  n1  n2       else         return getLCA root- gt right  n1  n2

User · Answer

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

User · Answer

The lowest common ancestor between two nodes node1 and node2 is the lowest node in a tree that has both nodes as descendants  The binary tree is traversed from the root node  until both nodes are found  Every time a node is visited  it is added to a dictionary  called parent   Once both nodes are found in the binary tree  the ancestors of node1 are obtained using the dictionary and added to a set  called ancestors   This step is followed in the same manner for node2  If the ancestor of node2 is present in the ancestors set for node1  it is the first common ancestor between them  Below is the iterative python solution implemented using stack and dictionary with the following points   A node can be a descendant of itself All nodes in the binary tree are unique node1 and node2 will exist in the binary tree  class Node      def   init   self  data None  left None  right None           self data    data         self left    left         self right   right  def lowest common ancestor root  node1  node2       parent    root  None      stack    root           while node1 not in parent or node2 not in parent          node   stack -1          stack pop           if node left              parent node left    node             stack append node left          if node right              parent node right    node             stack append node right           ancestors   set       while node1          ancestors add node1          node1   parent node1      while node2 not in ancestors          node2   parent node2           return node2 data  def main                Construct the below binary tree               30                                                            11      29                           8   12  25  14              root   Node 30      root left    Node 11      root right   Node 29      root left left    Node 8      root left right   Node 12      root right left    Node 25      root right right   Node 14       print lowest common ancestor root  root left left  root left right           11     print lowest common ancestor root  root left left  root left                 11     print lowest common ancestor root  root left left  root right right          30   if   name         main         main     The complexity of this approach is  O n

User · Answer

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

User · Answer

If it is full binary tree with children of node x as 2 x and 2 x 1 than there is a faster way to do it  int get bits unsigned int x      int high   31    int low   0 mid    while high gt  low        mid    high low  2      if 1 lt  lt mid  x        return mid 1      if 1 lt  lt mid lt x          low   mid 1            else         high   mid-1              if 1 lt  lt mid gt 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 gt ybits        diff   xbits-ybits      x   x  gt  gt  diff        else if xbits lt ybits        diff   ybits-xbits      y   y  gt  gt  diff        k   x y    kbits   get bits k     return y gt  gt kbits        How does it work        get bits needed to represent x  amp  y which using binary search is O log 32     the common prefix of binary notation of x  amp  y is the common ancestor   whichever is represented by larger no of bits is brought to same bit by k    diff   k   x y erazes common prefix of x  amp  y   find bits representing the remaining suffix   shift x or y by suffix bits to get common prefix which is the common ancestor       This works because basically divide the larger number by two recursively until both numbers are equal  That number is the common ancestor  Dividing is effectively the right shift opearation  So we need to find common prefix of two numbers to find the nearest ancestor

User · Answer

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 lt Treenode gt  q1   new LinkedList lt Treenode gt          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  amp  amp  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  amp  amp  v2           Treenode lca   lcaHelper head h1 h2           return lca value            return -1

[algorithm] How to find the lowest common ancestor of two nodes in any binary tree?

Examples related to algorithm

Examples related to binary-tree

Examples related to complexity-theory

Examples related to least-common-ancestor