Find the Lowest Common Ancestor in a Binary Search Tree

lca_bst.cpp

node* LCA_BST(node* root, node* c1, node* c2) {
    if(!c1 || !c2)
        return NULL;
    node* cur = root;
    while(cur) {    // returns NULL if root is NULL
        // cur key larger than both keys, LCA in the left subtree
        if(cur->key > c1->key && cur->key > c2->key)
            cur = cur->left;
        // cur key smaller than both keys, LCA in the right subtree
        else if(cur->key < c1->key && cur->key < c2->key)
            cur = cur->right;
        else
        // cur key is large than one key and smaller than the other
        // or cur key is equal to one of the keys
        // LCA is the cur node, break out the loop
            break;
    }
    return cur;
}