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