Lowest Common Ancestor of a Binary Search Tree (BST)
July 17, 2011 in binary tree
Given a binary search tree (BST), find the lowest common ancestor of two given nodes in the BST.
_______6______ / \ ___2__ ___8__ / \ / \ 0 _4 7 9 / \ 3 5
Using the above tree as an example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. But how about LCA of nodes 2 and 4? Should it be 6 or 2?
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).” Since a node can be a descendant of itself, the LCA of 2 and 4 should be 2, according to this definition.
Hint:
A topdown walk from the root of the tree is enough.
Solution:
There’s only three cases you need to consider.
 Both nodes are to the left of the tree.
 Both nodes are to the right of the tree.
 One node is on the left while the other is on the right.
For case 1), the LCA must be in its left subtree. Similar with case 2), LCA must be in its right subtree. For case 3), the current node must be the LCA.
Therefore, using a topdown approach, we traverse to the left/right subtree depends on the case of 1) or 2), until we reach case 3), which we concludes that we have found the LCA.
A careful reader might notice that we forgot to handle one extra case. What if the node itself is equal to one of the two nodes? This is the exact case from our earlier example! (The LCA of 2 and 4 should be 2). Therefore, we add case number 4):
The run time complexity is O(h), where h is the height of the BST. Translating this idea to code is straightforward (Note that we handle case 3) and 4) in the else statement to save us some extra typing ):
1 2 3 4 5 6 7 8 9  Node *LCA(Node *root, Node *p, Node *q) { if (!root  !p  !q) return NULL; if (max(p>data, q>data) < root>data) return LCA(root>left, p, q); else if (min(p>data, q>data) > root>data) return LCA(root>right, p, q); else return root; } 
You should realize quickly that the above code contains tail recursion. Converting the above function to an iterative one is left as an exercise to the reader.
Further Thoughts:
What if you are required to find the LCA of a binary tree (not a BST)? Check out my next post: Lowest Common Ancestor of a Binary Tree Part I to find out how.
Dee said on July 27, 2011
I think you are missing the case when either p or q is not a member of given tree.
Example: In your tree above, find LCA of 1 and 4. In that case your code would return 2, even when 1 is not present in tree.
Gordon said on April 6, 2013
I agree with you. And plus the case that one of them is not in the tree. But I question how far we should go. What if the given tree is not a valid tree? Do we need to take care of that? I think we should just ask the interviewers to clarify and move on from there.
Ogas Polt said on May 4, 2014
We won’t have to, the prerequisite is the tree is a valid binary search tree
Venki said on August 1, 2011
We need to check that both the nodes are present in tree (log N complexity), and then find LCA.
If the query is not valid, we should return null. Given below is wrapper.
parsh said on December 8, 2011
I think your soln. doesn’t work for finding LCA of 4 and 5 – which should be 2 but the code mention returns 4, which is incorrect.
parsh said on December 8, 2011
You can easily fix it by adding more if conditions,
if (root == null  root.data == a.data  root.data == b.data)
return null;
if (root.RightChild != null && (root.RightChild.data == a.data  root.RightChild.data == b.data))
return root;
if (root.LeftChild != null && (root.LeftChild.data == a.data  root.LeftChild.data == b.data))
return root;
visitor said on April 20, 2012
@Parsh—the ancestor should be 4 only…
kungfu_panda said on December 1, 2012
No, the code is correct, it should be 4 only.
Quoting from wikipedia: “The lowest common ancestor (LCA) is a concept in graph theory and computer science. Let T be a rooted tree with n nodes. The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”
Refer here – http://en.wikipedia.org/wiki/Lowest_common_ancestor
laggg said on August 22, 2013
The correct answer is 4.
Grace Chen said on December 12, 2011
It seems that the problem shall be clarified in the way that:
Not 2 nodes in the binary search tree can have the same value.
Simply specifying that a BST would not eleminate the above situation since:
binarysearchtree property:
• Let x be a node in a binary search tree. If y is a node in the left subtree of x, then key[y] ≤ key[x]. If y is a node in the right subtree of x, then key[x] ≤ key[y].
reader said on February 26, 2012
I have a question:
Is doing
Is
worse/wrong than using the max
that you use now?
reader said on February 26, 2012
I mean if (p>data data < data)
reader said on February 26, 2012
The formatting is messing it
reader said on February 26, 2012
I mean less than
Louise said on July 17, 2012
#include
using namespace std;
struct Node
{
Node(int value) : data(value)
{
pLeft = NULL;
pRight = NULL;
}
int data;
Node* pLeft;
Node* pRight;
};
Node* LowestCommonParent(Node* pBSTRoot, Node* pNode1, Node* pNode2)
{
if(NULL == pBSTRoot  NULL == pNode1  NULL == pNode2)
return NULL;
Node* pLess = NULL;
Node* pGreater = NULL;
if(pNode1>data data)
{
pLess = pNode1;
pGreater = pNode2;
}
else if(pNode1>data > pNode2>data)
{
pLess = pNode2;
pGreater = pNode1;
}
else
{
return NULL;
}
if((pLess>data data && pGreater>data > pBSTRoot>data) 
(pLess>data data && pGreater>data >= pBSTRoot>data))
{
return pBSTRoot;
}
else if(pGreater>data data)
{
return LowestCommonParent(pBSTRoot>pLeft, pLess, pGreater);
}
else if(pLess>data > pBSTRoot>data)
{
return LowestCommonParent(pBSTRoot>pRight, pLess, pGreater);
}
}
int main()
{
Node node0(6);
Node node1(2);
Node node2(8);
Node node3(0);
Node node4(4);
Node node5(7);
Node node6(9);
Node node7(3);
Node node8(5);
node0.pLeft = &node1;
node0.pRight = &node2;
node1.pLeft = &node3;
node1.pRight = &node4;
node2.pLeft = &node5;
node2.pRight = &node6;
node4.pLeft = &node7;
node4.pRight = &node8;
Node* pParent = LowestCommonParent(&node0, &node0, &node8);
cout <data << endl;
return 0;
}
geek said on February 24, 2013
The problem is to find LCA of a Binary tree and not BST.
KFL said on September 3, 2012
Only comparing data is not enough. I think you miss a case where two nodes has data that’re equal.
yifeng said on January 8, 2013
that won’t happen in BST
Jignesh said on July 17, 2013
public Node lcaBST(Node current, int n1, int n2) {
Node lca;
if (current == null)
return null;
if ((n1 current.key)
 (n1 == current.key && n2 > current.key)
 (n2 == current.key && n1 n1 && current.key > n2)
lca = lcaBST(current.leftChild, n1, n2);
else if (current.key < n1&& current.key < n2)
lca = lcaBST(current.rightChild, n1, n2);
else
lca = current;
return lca;
}</code
Ninja said on July 17, 2013
When i posted this code it looks like not the whole code got posted. How do i delete my comments
public Node lcaBST(Node current, int n1, int n2) {
Node lca;
if (current == null)
return null;
if ((n1 current.key)
 (n1 == current.key && n2 > current.key)
 (n2 == current.key && n1 n1 && current.key > n2)
lca = lcaBST(current.leftChild, n1, n2);
else if (current.key < n1&& current.key < n2)
lca = lcaBST(current.rightChild, n1, n2);
else
lca = current;
return lca;
}
Jignesh said on July 17, 2013
Kaidul said on October 10, 2014
Iterative approach:
bluenosetiger said on December 3, 2014
Please note BST definition allows left <= root. So it does not work on this case:
1. All the nodes have value 2
2. look for the LCA 2(2) and 2(3) while 2(1) is expected but 2(0) is retruned
2(0)

2(1)
 
2(2) 2(3)
bluenosetiger said on December 3, 2014
I was wrong. it is not BST since 2(3) should > 2(1)
bluenosetiger said on December 3, 2014
I was talking this case:
2(0)
left
2(1)
left
2(2)
looking for LCA 2(1) and 2(2). 2(1) is expected while 2(0) is returned.
bluenosetiger said on December 3, 2014
Here is my solution on this case
John said on January 1, 2015
Hi,
I don’t understand why the big O if this has been stated as O(n). As far as I can see, it is O(log n) as it pretty much resembles a BST search operation.
Could someone please clarify?
Thanks,
Abhi.
Anonymous said on January 7, 2015
What if the tree is skewed? Left or right skewed binary search tree
kaixuan said on January 9, 2015
quality and durability is concerned. You can get affordable and quality discount shoes from these sales nike tn requin . Brands like Adidasis best purchased on these online stores since they have good value for money when purchased via these stores. This is because these stores have constant sale periods and discount offers that happen to be running all throughout the year. AlsoFeature Articles, these discounts are pretty huge and you can save a lot of money by purchasing from these sites. The method of payment is also very convenient and easy to navigate. All you need to do is click a few buttons and avail the furthermore that you require at rates that are cheaper than that available. Adidas mainly focuses on its football kit that is of this particular equipments. Adidas remains to be the major company in delivering team kits for global football teams.
Sergey said on January 10, 2015
If the binary tree can contain duplicates, then we can build the tree with the following predicate:
n.left contains all elements n
In this case, we must handle possibility that on of the nodes we are searching can be duplicated in the tree.
consider the following integer valued BST:
2
/ \
2* 4
/
2
/
1*
Nodes to find lca for are marked with *, i.e. 1* and 2*. Original alg will return (uppermost) 2, not 2*.
Here is the corrected code:
Sergey said on January 10, 2015
If the binary tree can contain duplicates, then we can build the tree with the following predicate:
n.left contains all elements
n
n.right contains all elements
n
In this case, we must handle possibility that on of the nodes we are searching can be duplicated in the tree.
consider the following integer valued BST:
Nodes to find lca for are marked with *, i.e. 1* and 2*. Original alg will return (uppermost) 2, not 2*.
Here is the corrected code:
Sergey said on January 10, 2015
If the binary tree can contain duplicates, then we can build the tree with the following predicate:
n.left contains all elements
n.right contains all elements
In this case, we must handle possibility that on of the nodes we are searching can be duplicated in the tree.
consider the following integer valued BST:
Nodes to find lca for are marked with *, i.e. 1* and 2*. Original alg will return (uppermost) 2, not 2*.
Here is the corrected code:
bhnmjkle said on January 12, 2015
You might peek Cheap uggs sale fairly as well as complicated should you try out once again slits, component reduces Nike Tn Requin, as well as away make muscle tissue. Subsequent when you wish to enhance your personal quantity. you’ll often wear the form cradling lengthy kids uggs clearance evening wedding dress to be able to march the actual beautiful quantity. Nevertheless, in the event that you will notice small flaws or possibly body fat cells close to your present stomach outlet uggs for sale, gadget clothing or even a corset can easily hide which excess fat.That sheepskin linings believe mellow and even packed in addition get opinion blood circulation inside the ugg boots cheap brutish deal.
Qilu XIe said on February 12, 2015
Iterative Approach in C#:
Qilu XIe said on February 12, 2015
Iterative Approach in C#:
linfen said on February 15, 2015
Holiday shopping for exquisite gifts Look for online gift shopping India that carry a wide selection of classy gifts Nike Tn Requin at discount prices so you can do all or most of your holiday gift shopping at one place. This will save you time during the busy season as well as reduce costs on shipping. When shopping for gifts for children, be sure the items are durable and safe. Most children like to play rough, so the soft toys you buy make sure the it is of higher quality and the material of the toy is soft. Other special occasion gifts for women as well as men are flower arrangements, gift hampers, photo frames, box of chocolates etc. There are many classy gifts at discount prices if you know where to look. Check out products at an online gift shop India today for great bargains without sacrificing quality.