**Lowest common ancestor in binary search tree**

We saw how find K^{th} smallest element in binary search tree can easily be solve by using BST property which states that all nodes on left subtree of a node are smaller and all nodes on right subtree are greater than node itself. Another problem which uses this property of Binary Search Tree (BST) is finding **Lowest Common Ancestor commonly know as LCA.**

Problem statement is : given two nodes of BST, find lowest node which is parent of both given nodes, that is *least common ancestor (LCA).* For example in following tree, LCA of 25 and 37 is 30

Can we use property *“all nodes on left subtree smaller and all nodes on right subtree are greater than node”* to solve this problem? Lowest common ancestor of two nodes will be the node when path of two nodes diverge, i.e. one node is greater than current node and other is greater. For each candidate LCA, there are three cases to be considered:

**Case 1 : Two nodes are less than current node.**

In this case, there must be a node lower than current node on left subtree where these two nodes diverge. Hence, look for LCA in left subtree of current node.

**Case 2 : Two nodes are greater than current node**

In this case, there must be a node lower than current node on right subtree where these two nodes diverge. Hence, look for least common ancestor on right subtree of current node.

**Case 3: One of the two nodes is parent of other.**

In this case, LCA is parent node.

**Case 4 : One node is on left and other on right side of current node. **

Then current node is least common ancestor of two nodes.

**Implementation of lowest common ancestor algorithm**

#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 current node Found the LCA return */ if((root->value > val1 && root->value <= val2) || (root->value <= val1 && root->value >val2)){ return root->value; } /*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->right, val1, val2); } /*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->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) return createNode(value); 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; }

LCA candidates reduce by half with every comparison. In worst case, number of comparisons will be equal to depth of tree. Depth of a tree, given tree is not completely skewed, is roughly log N, hence complexity of this algorithm is logN. If the tree is completely skewed and there is parent child relationship between given nodes, then we need to compare N nodes and our complexity becomes O(N) in worst case.

Please share if there is something wrong or missing. If you are interested in contributing to website or have an interview problem to share, please contact us.