# Lowest Common Ancestor of a Binary Tree Part II

Given a binary tree, find the lowest common ancestor of two given nodes in the tree. Each node contains a parent pointer which links to its parent.

Note:
This is Part II of Lowest Common Ancestor of a Binary Tree. If you need to find the lowest common ancestor without parent pointers, please read Lowest Common Ancestor of a Binary Tree Part I.

```        _______3______
/              \
___5__          ___1__
/      \        /      \
6      _2       0       8
/  \
7   4```

If you are not so sure about the definition of lowest common ancestor (LCA), please refer to my previous post: Lowest Common Ancestor of a Binary Search Tree (BST) or the definition of LCA here. Using the tree above as an example, the LCA of nodes 5 and 1 is 3. Please note that LCA for nodes 5 and 4 is 5.

In my last post: Lowest Common Ancestor of a Binary Tree Part I, we have devised a recursive solution which finds the LCA in O(n) time. If each node has a pointer that link to its parent, could we devise a better solution?

Hint:
No recursion is needed. There is an easy solution which uses extra space. Could you eliminate the need of extra space?

An easy solution:
As we trace the two paths from both nodes up to the root, eventually it will merge into one single path. The LCA is the exact first intersection node where both paths merged into a single path. An easy solution is to use a hash table which records visited nodes as we trace both paths up to the root. Once we reached the first node which is already marked as visited, we immediately return that node as the LCA.

The run time complexity of this approach is O(h), where h is the tree’s height. The space complexity is also O(h), since it can mark at most 2h nodes.

The best solution:
A little creativity is needed here. Since we have the parent pointer, we could easily get the distance (height) of both nodes from the root. Once we knew both heights, we could subtract from one another and get the height’s difference (dh). If you observe carefully from the previous solution, the node which is closer to the root is always dh steps ahead of the deeper node. We could eliminate the need of marking visited nodes altogether. Why?

The reason is simple, if we advance the deeper node dh steps above, both nodes would be at the same depth. Then, we advance both nodes one level at a time. They would then eventually intersect at one node, which is the LCA of both nodes. If not, one of the node would eventually reach NULL (root’s parent), which we conclude that both nodes are not in the same tree. However, that part of code shouldn’t be reached, since the problem statement assumed that both nodes are in the same tree.

Further Thoughts:
Isn’t the solution above neat? It requires some creative thought and is quite subtle.

A variation of this problem which seemed to be more popular is:

Given two singly linked lists and they both intersect at one point (ie, forming a Y shaped list). Find where the two linked lists merge.

I am sure you know how to answer this question now 🙂

VN:F [1.9.22_1171]
Rating: 4.8/5 (76 votes cast)
Lowest Common Ancestor of a Binary Tree Part II, 4.8 out of 5 based on 76 ratings

## 32 thoughts on “Lowest Common Ancestor of a Binary Tree Part II”

1. Pankaj

Please try to remove add if possible.
Instead add a paypal option so that those who get benefit from your blog can support this hard work of yours 😀

VA:F [1.9.22_1171]
-16
2. maxq

There seems to be a bug in your code?

Node *LCA(Node *root, Node *p, Node *q) {
hash_set visited;
while (p || q) {
if (p) {
if (!visited.insert(p).second)
return p; // insert p failed (p exists in the table)
p = p->parent;
}
if (q) {
if (!visited.insert(p).second) parent;
}
}
return NULL;

VA:F [1.9.22_1171]
+1
1. 1337c0d3r Post author

Are you saying that on line 10:
(!visited.insert(p).second)
should be:
(!visited.insert(q).second)

If that is, this is a mistake and thanks for pointing that out. I will correct the post later.

VN:F [1.9.22_1171]
0
1. protocol

What is “second” in (!visited.insert(q).second) ?

I know in Java, for “visited.add(q)”, if q exists, it will return false. But here, what is the mean of “second” ?

VN:F [1.9.22_1171]
0
1. 1337c0d3r Post author

The insert() function returns a pair.

The insert member function returns a pair whose bool component returns true if an insertion was make and false if the hash_set already contained an element whose key had an equivalent value in the ordering

http://msdn.microsoft.com/en-us/library/2t5cf4t8%28v=vs.80%29.aspx

VN:F [1.9.22_1171]
0
3. Chetan Sharma

Various solution to the Y shaped linked list problem exists, one of them being:

Start traversing first list setting the next pointer to NULL in the process. Now start traversing the second list until the next pointer of a node is not NULL. At this point the current node is the intersecting node. Though this solution requires modification to the list but is more efficient as you need to traverse the list only once

VA:F [1.9.22_1171]
-1
4. fangstar

For the Y shaped linked list problem, instead of difference in height we need to calculate the difference in length between the linked lists right?
Then do the similar advancement on the longer length, and then iterate for a match?

TIY

VA:F [1.9.22_1171]
0
5. Eugene Kirpichov

The solution is indeed neat, but I would not call it “best” in all situations. It requires at least traversing both nodes to the root, whereas the “easy” solution may stop much earlier than that.

VA:F [1.9.22_1171]
+3
6. 景泰蓝

Node *LCA(Node *root, Node *p, Node *q){
Node * q_path[MAX] , p_path[MAX];
int qi=0, pi=0;
while(q) { q_path[qi++]=q; q=q->parent ;}
while(p) { p_path[pi++]}=p; p=p->parent; }
while(qi>=0 && pi>=0){ if(q_path[–qi] != p_path[–pi]) return p_path[qi] ; }
return NULL;

}

VN:F [1.9.22_1171]
0
1. alexlee

your code “while(qi>=0 && pi>=0){ if(q_path[–qi] != p_path[–pi]) return p_path[qi] ; }”has a question,I think should return p_path[qi+1];

VA:F [1.9.22_1171]
0
7. Raja

The LCA of 6 and 2 in the example should be 5 or 3 ? Since its lowest common ancestor – Shouldnt it be 3 ?

But the code given would give us 5 as the answer. Please clarify ?

Thanks,
Raja.

VA:F [1.9.22_1171]
-1
8. Ganesh R

You are using parent.. But the actual structure of a Binary tree should be
struct tree
{
struct tree *lchild;
struct tree *rchild;
int element;
};

If additional varialbles or terms added, can it called a Binary tree???

VN:F [1.9.22_1171]
-1
1. George

Yes, a binary tree doesn’t stop being a binary tree if you add a pointer to the parent node. The solution provided is indeed very creative

VA:F [1.9.22_1171]
+1
2. Sumit

@ Ganesh , I think it should be , for node structure can be modified , yet the overall structure doesn’t cease to be a binary tree , I know I had applied the exactly same approach when asked to find LCA in Univ Exams , only to score a zero 🙂 for not following the soln they had in the answer key ! Damn !!
we may avoid swapping by using minptr=minheight(h1,h2) and then proceed as is

VN:F [1.9.22_1171]
0
9. Daniel

There is a better solution…
The suggested solution is o(depth of tree), there is a solution in o(distance of two nodes).

1.Note: Once you find a common ancestor, you can find the differences between the two nodes heights, and find the lowest common ancestor.

2. In order to find a common ancesstor in o(distance) you can walk up in the tree alternately with each pointer in the following way:
a. first you will go with the first pointer 1 step.
b. with the second pointer 2 steps.
c. with the first pointer 4 steps.. etc
where in each step you compare the pointers, and you stop once they are equal.

On the iteration where the number of steps is >= distance of the two nodes, you will find some common ancestor o(distance).

VA:F [1.9.22_1171]
+1
10. Tong Liu

it is like another question finding intersection of two linked list

VN:F [1.9.22_1171]
0
11. Raj

COuld you please explain it.I did not understand How do we go back like p=p->parents.

VA:F [1.9.22_1171]
+1
12. Partha Pratim Sirker

Although it is similar to a Y shaped linkedlist problem, the solution would involve find out the path of the nodes separately which is of O(n) operation. So in total we will do two iteration of O(n) and then O(log n) to find out the Y junction. (Assuming there is no parent pointer). I found this solution better where there is only one iteration and it is of O(n) complexity. It is done with a single post-order traversal. http://www.dsalgo.com/LowestCommonAncestor.php

VA:F [1.9.22_1171]
0
13. Prateek Caire

How about this one.Move one of the nodes up and delink the parent by putting null to parent pointer.Move second node up till we do not find delinked parent. That node is LCA. Solution, however, alters tree structure

VA:F [1.9.22_1171]
+1
1. Kevin Hou

Great job! This method works.

VA:F [1.9.22_1171]
0
14. DaShan

I don’t think computing the nodes’ heights is necessary:

-Assuming we store the “root-to-node” path in a stack
-Then going down to child node is represented by a stack “push”, and a backtrack is achieved by a stack pop
-(1) After finding the 1st node, we have a stack that stores the path from the root to the 1st node
-(2) Then we continue the traversal, by “pop”, “push”, “push”, …, until reaching the 2nd node
-between (1) and (2), a prefix of the stack, namely from the root to the LCA, will not change
-therefore, we can use a “watermark pointer” to maintain “the lowest element of the stack content at (1) that survives till (2) is done”.
-Once (2) is done, the above “watermark pointer” points to the LCA.

VN:F [1.9.22_1171]
0
1. Siyong

That would require extra memory.

VN:F [1.9.22_1171]
0
15. Chris Tsang

Why return NULL when p and q is both Null? To handle the situation when p and q is not in the same tree?

VN:F [1.9.22_1171]
0
16. hypnotize

If some one needs to be updated with hottest technologies
then he must be pay a quick visit this web site and be up to date everyday.

VA:F [1.9.22_1171]
0
17. およそ1年前、私は私のマーク・カーソンkaラ・スポーツ腕時計はどうなるのだろう、ダイヤルと手を設計したが、特定の思想は当時のストラップに与えられました。私は、バーゼル2015年か

およそ1年前、私は私のマーク・カーソンkaラ・スポーツ腕時計はどうなるのだろう、ダイヤルと手を設計したが、特定の思想は当時のストラップに与えられました。私は、バーゼル2015年から帰ったとき、私は座った一つのゴールの設計は、高セキュリティストラップシステムを利用することができたのは、曲がった金属片の「私のマーク・カーソンkaラの場合にnatoストラップのより多くの保安を提供するツールと特徴的なマッチョの観察を提供する。 http://www.bestevance.com/rolex/mester/index.htm

VA:F [1.9.22_1171]
0