663 views

2 Answers

Best answer
1 votes
1 votes
#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 by
1 votes
1 votes
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?

please verify this

No related questions found