+1 vote
93 views
can anyone define the procedure to find the common ancestor of any two given nodes in balanced BST..??
asked in DS | 93 views

+1 vote
#define BIGGER 1
#define SMALLER -1
#define EQUAL 0

int compare(int x,int y) {
if(x == y) return EQUAL;
else if(x < y) return SMALLER;
els return BIGGER;
}

struct node* find_LCA(struct node *root,int a,int b) {

// I have assumed that a and b exist in the tree already

if(root != NULL) {
// compare this node with a
int res1 = compare(a,root->data);
// compare this node with b
int res2 = compare(b,root->data);
}
// is any one of a,b is equal to this node value
// then return this node
if(res1 == EQUAL || res2 == EQUAL) {
return root;
}
//  a and b are on different subtree
else if(res1 != res2) {
return root;
}
else {
// one of the following recursive call will execute

if(res1 == BIGGER) {				// or res2 == BIGGER same thing
return find_LCA(root->right_child,a,b);
}else {
return find_LCA(root->left_child,a,b);
}
}

}
• Best case $O(1)$
• Worst case $O(\log n)$
• Checking of null pointers before a recursive call and a=b  or any other code handling issue have has been eliminated for simplicity.
edited
For normal binary tree or any rooted tree, and with multiple queries (a,b), this LCA problem is of great interest and very interesting.
+1 vote
will it be like -

first comapring A nd B with the root node..if A< root and B > root then root is the common ancestor..

if A< ROOT & B is also < root then again calling same function with root-> left

if A>root and B is also > root then again calling same function with root -> right

its T(n) will be O(log n)..right?