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

StackOverflow https://stackoverflow.com/questions/9046307

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 :

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?

Was it helpful?

Solution

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)

OTHER TIPS

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

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->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 In Action

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 && right != null) {
      return root;
   }

   return (left != null) ? left : right; 
}

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

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.

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

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.

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.

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

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

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

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 < root.val > q.val and root.left or \
           p.val > root.val < q.val and root.right
    return self.lowestCommonAncestor(next, p, q) if next else root

Java

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    return (root.val - p.val) * (root.val - q.val) < 1 ? root :
           lowestCommonAncestor(p.val < root.val ? root.left : root.right, p, q);
}

Node *LCA(Node *root, Node *p, Node *q) {
  if (!root) return NULL;
  if (root == p || root == q) return root;
  Node *L = LCA(root->left, p, q);
  Node *R = LCA(root->right, p, q);
  if (L && R) return root;  // if p and q are on both sides
  return L ? L : R;  // either one of p,q is on one side OR p,q is not in L&R subtrees
}

Consider this tree enter image description here

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 & 11 in preorder we have =>7,3,1,0,2,6,4,5,12,9 before 8 & 11

9 is the first common number that occurs after 8& 11 in postorder and before 8 & 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

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

How does it work

  1. get bits needed to represent x & y which using binary search is O(log(32))
  2. the common prefix of binary notation of x & y is the common ancestor
  3. whichever is represented by larger no of bits is brought to same bit by k >> diff
  4. k = x^y erazes common prefix of x & y
  5. find bits representing the remaining suffix
  6. 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

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) => {
        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
    }
  }

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)

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

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

How to use it:

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

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

I found a solution

  1. Take inorder
  2. Take preorder
  3. 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.

Here is what I think,

  1. Find the route for the fist node , store it on to arr1.
  2. Start finding the route for the 2 node , while doing so check every value from root to arr1.
  3. time when value differs , exit. Old matched value is the LCA.

Complexity : step 1 : O(n) , step 2 =~ O(n) , total =~ O(n).

Here are two approaches in c# (.net) (both discussed above) for reference:

  1. 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.

  2. 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)

  3. Just for the completion (not related to question), LCA in BST (O(log(N))

  4. 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 && 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("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;
        }

Solution by keeping track of paths of both nodes:

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

where FindNodeAndPath is defined as

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) - 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 > e1 ) && (iterativeNode.Element > e2))
                {
                    iterativeNode = iterativeNode.Left;
                }
                else if((iterativeNode.Element < e1) && (iterativeNode.Element < e2))
                {
                    iterativeNode = iterativeNode.Right;
                }
                else
                {
                    //i.e; either iterative node is equal to e1 or e2 or in between e1 and e2
                    return iterativeNode;
                }
            }
            //control will never come here
            return leastCommonAcncestor;
        }

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

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

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


}

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

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

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

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
    }
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top