Lowest common ancestor in binary tree

Lowest common ancestor (LCA) in BST

Given a binary search tree and two nodes, find the lowest node which is the parent of both given nodes, that is the lowest common ancestor (LCA). For example, in the following tree, LCA of 6 and 1 is node(5), whereas lowest common ancestor of node 17 and 6 would be node(10).

lowest common ancestor lca

Lowest common ancestor : Thoughts

What is the condition for a node to be LCA of two nodes?  If paths for given nodes diverges from the node, then node is lowest common ancestor. While path is common for both the nodes, nodes are common ancestor but they are not lowest or least. How can we find where paths are diverging?

Paths are diverging when one node is on left subtree and another node is on right subtree of the node. Brute force solution would be to find one node and then go up the tree and see at what parent node, other given node falls on the opposite subtree.

Implementation wise, traverse to node 1 and node 2 and store both paths on the stack. Then pop from two stacks till you find the same node on both paths, that node would be the lowest common ancestor. There will be two scans of the tree and additional space complexity to store paths which in the worst case be O(n).

However, the brute force solution does not use the property of a binary search tree. Property is that all the nodes on the left side of a node are smaller and all the nodes on the right side of a node are greater than node. Can we use that property to solve this problem?

Basic idea is to return the node if it is found in any of the subtrees. At any node, search for both given nodes in the left subtree.  If we get a non-empty node returned from the left subtree, there is at least one of the two nodes is on left subtree.

Again, search in right subtree these two nodes, if a non-empty node is returned from the right subtree, that means at least one of the node is on right subtree.

What does it means if we have a non-empty node on both left and right subtree? It means two nodes are on the left and right subtree, one on each side. It means the root node is the lowest common ancestor.

What if one of the returned nodes is empty? It means both nodes are on one side of the root node, and we should return the upwards the non-empty node returned.

Let’s take an example and see how does it work? Given the below tree, find the lowest common ancestor of node(1) and node(9).

lowest common anestor in binary tree

Start with the node(10) and look for the left subtree for both node(1) and node(9). Go down all the way to the node(1), at the time, we return 1 as the node as node.value is equal to one of the nodes.

lowest common anestor in binary tree

lowest common anestor in binary treeAt node(5), we have got node(1) return from left subtree. We will search for node(1) and node(9) on right subtree. We go all the way to node(6), which is leaf node.

least common ancestor in binary search tree

At node(8), left subtree returns nothing as none of the nodes in the left subtree of node(8). However, right subtree returns node(9).

lowest common ancestor

As per our algorithm, if either of subtree returns non-empty node, we return the node return from the subtree.

lca in binary search tree

At node(5), we get a non-empty node from right subtree and we already know, from the left subtree, we got node(1). At this point at node(5), we have both left and right subtree returning non-empty node, hence return the node(5).

lca in binary treee

Two nodes will be searched on the right subtree of node(10), which will return nothing, hence, final lowest common ancestor will be node(5).

Lowest common ancestor : Implementation

#include<stdio.h>
#include<stdlib.h>
 
struct node{
	int value;
	struct node *left;
	struct node *right;
};

typedef struct node Node;

Node * findLCA(Node *root, int val1, int val2)
{
    // Base case
    if (root == NULL) return NULL;
 
    /* If either val1 or val2 matches with root's key, 
       report the presence by returning the root
       (Note that if a key is the ancestor of other,
       then the ancestor key becomes LCA 
   */
    if (root->key == val1 || root->key == val2)
        return root;
 
    // Look for keys in left and right subtrees
    Node *left  = findLCA(root->left, val1, val2);
    Node *right = findLCA(root->right, val1, val2);
 
    /* If both of the above calls return Non-NULL,
       then one key is present in once subtree
       and other is present in other,
       So this node is the LCA */
    if (left && right)  return root;
 
    // Otherwise check if left subtree or right subtree is LCA
    return (left != NULL)? left : right;
}

Node * createNode(int value){
  Node *newNode =  (Node *)malloc(sizeof(Node));
  
  newNode->value = value;
  newNode->right= NULL;
  newNode->left = NULL;
  
  return newNode;
}

Node * addNode(Node *node, int value){
  if(node == NULL){
      return createNode(value);
  }
  else{
     if (node->value > value){
        node->left = addNode(node->left, value);
      }
      else{
        node->right = addNode(node->right, value);
      }
  }
  return node;
}
 
/* Driver program for the function written above */
int main(){
  Node *root = NULL;
  //Creating a binary tree
  root = addNode(root,30);
  root = addNode(root,20);
  root = addNode(root,15);
  root = addNode(root,25);
  root = addNode(root,40);
  root = addNode(root,37);
  root = addNode(root,45);
  
  printf("\n least common ancestor: %d ",
      leastCommonAncestor(root, 15, 25));
  
  return 0;
}

Below implementation only works for binary search tree and not for the binary tree as above method works.

#include<stdio.h>
#include<stdlib.h>
 
struct node{
	int value;
	struct node *left;
	struct node *right;
};

typedef struct node Node;

int leastCommonAncestor(Node *root, int val1, int val2){

 	if(!root)
       return -1;

 	if(root->value == val1 || root->value == val2)
    	return root->value;

 	/* Case 3: If one value is less and other greater
             than the current node
             Found the LCS return */
 	if((root->value > val1 && root->value <= val2) ||
  		(root->value <= val1 && root->value >val2)){
             return root->value;
 	}
  	/*Case 2 : If Both values are greater than current node, 
           look in right subtree */
 	else if(root->value < val1 && root->value <val2){
        return leastCommonAncestor(root->right, val1, val2);
 	}
 	/*Case 1 : If Both values are less than current node,
           look in left subtree */
 	else if(root->value > val1 && root->value > val2){
        return leastCommonAncestor(root->left, val1, val2);
 	}
}

Node * createNode(int value){
  Node *newNode =  (Node *)malloc(sizeof(Node));
  
  newNode->value = value;
  newNode->right= NULL;
  newNode->left = NULL;
  
  return newNode;
  
}

Node * addNode(Node *node, int value){
  if(node == NULL){
      return createNode(value);
  }
  else{
     if (node->value > value){
        node->left = addNode(node->left, value);
      }
      else{
        node->right = addNode(node->right, value);
      }
  }
  return node;
}
 
/* Driver program for the function written above */
int main(){
  Node *root = NULL;
  //Creating a binary tree
  root = addNode(root,30);
  root = addNode(root,20);
  root = addNode(root,15);
  root = addNode(root,25);
  root = addNode(root,40);
  root = addNode(root,37);
  root = addNode(root,45);
  
  printf("\n least common ancestor: %d ",
      leastCommonAncestor(root, 15, 25));
  
  return 0;
}

The worst complexity of the algorithm to find the lowest common ancestor in a binary tree is O(n). Also, keep in mind that recursion is involved. More skewed the tree, more stack frames on the stack and more the chances that stack will overflow.

This problem is solved using on traversal of tree and managing states when returning from recursive calls.

Please share if there is something wrong or missing. If you are willing to contribute and share your knowledge with thousands of learners across the world, please reach out to us at communications@algorithmsandme.com