algorithm Il più basso antenato comune in una BST


Esempio

Considera il BST:

inserisci la descrizione dell'immagine qui

Il più basso antenato comune tra 22 e 26 è 24

Il più basso antenato comune tra 26 e 49 è 46

L'antenato più comune di 22 e 24 è 24

La proprietà dell'albero di ricerca binaria può essere utilizzata per trovare l'antenato più basso dei nodi

Codice Psuedo:

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);
      }
        }