# Lowest Common Ancestor of a Binary Search Tree (BST)

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 top-down walk from the root of the tree is enough.

Solution:
There’s only three cases you need to consider.

1. Both nodes are to the left of the tree.
2. Both nodes are to the right of the tree.
3. 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 top-down 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):

4. When the current node equals to either of the two nodes, this node must be the LCA too.

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 😉 ):

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.

VN:F [1.9.22_1171]
Rating: 4.7/5 (52 votes cast)
Lowest Common Ancestor of a Binary Search Tree (BST), 4.7 out of 5 based on 52 ratings

## 40 thoughts on “Lowest Common Ancestor of a Binary Search Tree (BST)”

1. Dee

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.

VA:F [1.9.22_1171]
-8
1. Gordon

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.

VN:F [1.9.22_1171]
+6
1. Ogas Polt

We won’t have to, the prerequisite is the tree is a valid binary search tree

VA:F [1.9.22_1171]
0
2. Venki

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.

VA:F [1.9.22_1171]
+6
3. parsh

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.

VA:F [1.9.22_1171]
0
1. parsh

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;

VA:F [1.9.22_1171]
0
1. visitor

@Parsh—the ancestor should be 4 only…

VA:F [1.9.22_1171]
+2
2. kungfu_panda

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

VA:F [1.9.22_1171]
0
3. laggg

The correct answer is 4.

VA:F [1.9.22_1171]
0
4. Grace Chen

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:
binarysearch-tree 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].

VN:F [1.9.22_1171]
+1
5. reader

I have a question:
Is doing
Is

worse/wrong than using the max

that you use now?

VA:F [1.9.22_1171]
0
6. reader

I mean if (p->data data < data)

VA:F [1.9.22_1171]
0
1. reader

The formatting is messing it

VA:F [1.9.22_1171]
0
2. reader

I mean less than

VA:F [1.9.22_1171]
0
7. Louise

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

VN:F [1.9.22_1171]
0
1. geek

The problem is to find LCA of a Binary tree and not BST.

VA:F [1.9.22_1171]
0
8. KFL

Only comparing data is not enough. I think you miss a case where two nodes has data that’re equal.

VN:F [1.9.22_1171]
0
1. yifeng

that won’t happen in BST

VA:F [1.9.22_1171]
+2
9. Jignesh

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

VA:F [1.9.22_1171]
0
1. Ninja

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

VN:F [1.9.22_1171]
0
10. Jignesh

VA:F [1.9.22_1171]
0
11. Kaidul

Iterative approach:

VA:F [1.9.22_1171]
0
12. bluenosetiger

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)

VA:F [1.9.22_1171]
0
1. bluenosetiger

I was wrong. it is not BST since 2(3) should > 2(1)

VA:F [1.9.22_1171]
0
13. bluenosetiger

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.

VA:F [1.9.22_1171]
0
1. bluenosetiger

Here is my solution on this case

VA:F [1.9.22_1171]
0
14. John

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.

VA:F [1.9.22_1171]
0
1. Anonymous

What if the tree is skewed? Left or right skewed binary search tree

VA:F [1.9.22_1171]
0
15. Sergey

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:

VA:F [1.9.22_1171]
0
16. Sergey

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:

VA:F [1.9.22_1171]
0
17. Sergey

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:

VA:F [1.9.22_1171]
0
18. Qilu XIe

Iterative Approach in C#:

VA:F [1.9.22_1171]
0
19. Qilu XIe

Iterative Approach in C#:

VA:F [1.9.22_1171]
0
20. Jun

I came up with the same complexity solution that would work for the general Binary Tree.

TreeNode LCA(TreeNode root, TreeNode node1, TreeNode node2) {
if (root == null)
return null;

visit(root, node1, node2);
return lca_node;
}

int visit(TreeNode root, TreeNode node1, TreeNode node2) {
// 1 if node1 is present below, 2 if node2, 3 if both.
int result = 0;
if (root != null)
result = visit(root.left, node1, node2) + visit(root.right, node1, node2);

if (root == node1)
result += 1;
else if (root == node2)
result += 2;

if (result == 3 && lca_node == null)
// pick up the first root with the result 3
lca_node = root;

return result;
}

VN:F [1.9.22_1171]
0
21. Mahmoud Emam

what if the input was 3 and 5 for your example tree.
your result would be 4 which is not correct and it should be 2 according to LCA definition!!

VA:F [1.9.22_1171]
0
22. ものhalios腕時計でのハードと高速走行しているが、最近いじめのデザインは2013年にリリースされる3つの今後のモデルのための。新しいモデルの小さな部分と呼ばれるダイバースパンのブロ

ものhalios腕時計でのハードと高速走行しているが、最近いじめのデザインは2013年にリリースされる3つの今後のモデルのための。新しいモデルの小さな部分と呼ばれるダイバースパンのブロンズ製の箱入りの兄弟と、デルフィンというより大きくてより深刻なダイバー。 http://www.wtobrand.com/lv20.html

VA:F [1.9.22_1171]
0