February 16, 2012

Lowest Common Ancestor

Question: Given values of two nodes in a binary search tree, write a function to find lowest common ancestor of these two nodes. Lowest common ancestor can be described as a parent node that is common and closest to both the given nodes. (If both the nodes are present in the tree the NULL check is not required, also assuming that -1 is an invalid data value.)  


Time Complexity: O(log(n))

int
lowest_common_ancestor(tree *t, int value1, int value2)
{
    // Check required if nodes with input 
    // values are not present in the tree
    if (t == NULL) {
        return -1;
    }


    if (t->data < value1 && t->data < value2) {
        return lowest_common_ancestor(t->right, value1, value2);
    } else if (t->data > value1 && t->data > value2) {
        return lowest_common_ancestor(t->left, value1, value2);
    } else {
        return t->data;
    }

}

No comments:

Post a Comment