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.

C++:
01 Node* lowestCommonAncestor(Node* head, Node* p, Node* q)
02 {
03     map <Node*, int> m;
04     Node* tmp=p;
05     while(tmp!=NULL){
06         m[tmp]=1;
07         tmp=tmp->parent;
08     }
09     tmp=q;
10     while(tmp!=NULL){
11         if(m.find(tmp)!=m.end())
12             return tmp;
13         tmp=tmp->parent;
14     }
15     return NULL;
16 }
If we do not allow to use map, we can count the steps to the root for each node. Move the lower node up and then move two nodes up to the root together and check the first time they meet.
C++:
01 Node* lowestCommonAncestorStep(Node* head, Node* p, Node* q)
02 {
03     int cnta=0;
04     int cntb=0;
05     Node* tmp=p;
06     while(tmp!=NULL){
07         cnta++;
08         tmp=tmp->parent;
09     }
10     tmp=q;
11     while(tmp!=NULL){
12         cntb++;
13         tmp=tmp->parent;
14     }
15     while(cnta>cntb){
16         p=p->parent;
17         cnta;
18     }
19     while(cntb>cnta){
20         q=q->parent;
21         cntb;
22     }
23     while(p&&q){
24         if(p==q)
25             return p;
26         p=p->parent;
27         q=q->parent;
28     }
29     return NULL;
30 }
Advertisements
This entry was posted in Hashtable and Map, Tree. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s