#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.