Introduction
In this blog, we will discuss a binary search tree problem that has been asked frequently in Interviews and also is one of the most important sets of binary search tree algorithms.
The problem is to find the Lowest Common Ancestor in a Binary Search Tree.
A common prerequisite before any BST problem is the knowledge of recursion because, without understanding recursion, things can become very difficult for you to understand. Before we proceed, we must know what a Binary Search Tree is.
A Binary Search Tree is a binary tree that follows a special property that any node in the left subtree in the BST is smaller than the root node and any node in the right subtree in the BST is greater than the root node. Every subtree of the BST must follow this property,
Also see, Data Structures
Letâ€™s look at the problem first.
We are given a reference or a pointer to the root of a binary search tree. Now our task is to find the Lowest Common Ancestor in a Binary Search Tree.
Letâ€™s understand the Lowest Common Ancestorâ€™s definition.
Let a and b be two nodes present in a binary search tree. Then, LCA is defined as the lowest node in the binary search tree, whose descendants are a and b, respectively.
Also see, Difference Between Binary Tree and Binary Search Tree
Note: A node is a descendant of itself.
Given a binary Search tree,
Input: reference/pointer to nodes 3 and 1.
Output: reference/pointer to node 2.
What are the common ancestors of nodes 3 and 1? They are nodes 4 and 2.
Now, by definition, out of nodes 4 and 2, which one is the lowest node?
The answer is Node 2. Hence the LCA of nodes 3 and 1 is node 2.
Letâ€™s look at the approach to this question.
Must Read Recursive Binary Search.
Approach
Try recalling how to find the Lowest Common Ancestor of a Binary Tree. Then, you will get a sense of approaching this problem, and you will notice that special property followed by any BST makes the problem much more trivial than finding the LCA in a binary tree of 2 given nodes.
Letâ€™s discuss some ideas.

Notice how we traverse down the tree to reach both the nodes; if both of them are smaller than the root node, we move to the left, and if they both are greater than the root node, we will go on the right.

But how do we traverse when we have one of the values smaller than the root node and the other greater than the root node?
If one tends to observe in case b), when we reach the LCA, it will segregate the 2 nodes in the left and the right subtree. Hence, we encounter this case, we can declare the root node of the subtree as the Lowest Common Ancestor of a Binary Search Tree.
See the below example to visualize the above case where we want to find the LCA of 1 and 3.
When we start traversing from root node 4 we see that nodes 1 and 3 lie in the same subtree but when we reach node 2, we see that nodes 1 and 3 now lie in different subtrees. Hence we declare node 2 as the LCA.

Another case we might encounter is if one of the given 2 nodes occurs before the other and the other node lies in its left or right subtree, then the node which occurs first is our LCA.
(NOTE: this is a case that has been discussed separately so that we donâ€™t miss out on any case, but it will be handled by the case (b) discussed before this case (Why?) since out of the 2 nodes, the node that occurred first will split both nodes into different subtrees. Hence the node occurring first will be our LCA).
So approach can be formulated as:
 If both given nodes are smaller than the root node, traverse the left subtree.
 If both given nodes are greater than the root node, traverse the right subtree.
 If cases (1) and (2) donâ€™t satisfy, return the current subtree root node.
PseudoCode
Algorithm
___________________________________________________________________
procedure findLCAinBST( rootNode, nodeA, nodeB ):
___________________________________________________________________
1. If rootNode is NIL do # base case
2. return rootNode
3. end if
4. if nodeA.data < rootNode.data and nodeB.data < rootNode.data do
5. return findLCAinBST(rootNode.left, nodeA, nodeB)
6. end if
7. if nodeA.data > rootNode.data and nodeB.data > rootNode.data do
8. return findLCAinBST(rootNode.right, nodeA, nodeB)
9. end if
10. else do
11. return rootNode
12. end procedure
___________________________________________________________________
CODE IN C++
Now, letâ€™s have a look at the Lowest Common Ancestor in a Binary Search Tree:
//C++ program to find the Lowest Common Ancestor of 2 nodes in a BST
#include <bits/stdc++.h>
using namespace std;
// struct Node to create Nodes in the Binary search tree
struct Node{
int data; // value of the node
Node *left; // left child
Node *right; // right child
Node(int d)
{
this>data = d;
this>left = nullptr;
this>right = nullptr;
}
};
// function that finds the LCA of given 2 nodes present in the binary search tree
Node* findLCAinBST(Node* root, Node *nodeA, Node *nodeB){
if(root==nullptr) // base case
return root;
// if both nodes a and b are smaller than root node
if(nodeA>data < root>data and nodeB>data < root>data)
return findLCAinBST(root>left, nodeA, nodeB); // go to the left subtree
// if both nodes a and b are greater than root node
if(nodeA>data > root>data and nodeB>data > root>data)
return findLCAinBST(root>right, nodeA, nodeB); // go to the right subtree
// return the root since this is the LCA
return root;
}
int main(){
// size of the binary search tree
int size = 6;
// creating a sample binary search tree
Node *root = new Node(4);
root>left = new Node(2);
root>right = new Node(6);
root>right>left = new Node(5);
root>left>left = new Node(1);
root>left>right = new Node(3);
// find the pointer to the LCA node for the nodes with value 1 and 3.
Node *LCA = findLCAinBST(root, root>left>left, root>left>right);
cout<<"The lowest common ancestor of the given node A and node B is: "<<LCA>data;
return 0;
}
Output
The lowest common ancestor of the given node A and node B is: 2 
Time Complexity: O(h)
The above algorithm takes O(h) time complexity, where h is the height of the binary search tree. We traverse the binary search tree along with its height, and the maximum we can go up is till we reach its height.
Space complexity: O(h) at the worst case, as we are recursively traversing the BST.