-
Notifications
You must be signed in to change notification settings - Fork 1
/
Kth common ancestor in BST.cpp
52 lines (50 loc) · 1.14 KB
/
Kth common ancestor in BST.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution
{
public:
void getParent(Node* root, map<Node*, Node*> &m)
{
if(root==NULL) return;
if(root->left){
m[root->left] = root;
getParent(root->left, m);
}
if(root->right){
m[root->right] = root;
getParent(root->right, m);
}
}
Node* LCA(Node* root, int p, int q){
if(root==NULL){
return NULL;
}
if(root->data==p){
return root;
}
if(root->data==q){
return root;
}
Node* l = LCA(root->left, p, q);
Node* r = LCA(root->right, p, q);
if(l==NULL){
return r;
}
if(r==NULL ){
return l;
}
return root;
}
int kthCommonAncestor(Node *root, int k,int x, int y)
{
if(root==NULL) return -1;
Node *lca = LCA(root, x, y);
map<Node*, Node*> m;
m[root] = NULL;
getParent(root, m);
if(lca==NULL) return -1;
while(--k){
lca = m[lca];
if(lca==NULL) return -1;
}
return lca->data;
}
};