Horje

LOWEST common ancestor in a bst - Binary Search Trees - Algorithm
Learn
Algorithm - Binary Search Trees - Lowest common ancestor in a bst
Lowest common ancestor in a BST

Consider the BST:

enter image description here (opens new window)

Lowest common ancestor of 22 and 26 is 24

Lowest common ancestor of 26 and 49 is 46

Lowest common ancestor of 22 and 24 is 24

Binary search tree property can be used for finding nodes lowest ancestor

Psuedo code:

lowestCommonAncestor(root,node1, node2){

if(root == NULL)    
return NULL;



 else if(node1->data == root->data || node2->data== root->data)    
    return root;
    
    else if((node1->data <= root->data && node2->data > root->data)
              || (node2->data <= root->data && node1->data > root->data)){
        
             return root;
    }
    
    else if(root->data > max(node1->data,node2->data)){
            return lowestCommonAncestor(root->left, node1, node2);
    }
        
        else {
            return lowestCommonAncestor(root->right, node1, node2);
      }
        }


Read Article
https://develop.horje.com/learn/1434/reference

 

Horje