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

}

Missing Number

Question: Given an array of integers of size n. This array has integer values starting from x, incrementing by 1. The final array element is n+x (instead of n + x - 1) i.e. it is missing one integer in between. Write a function to identify this missing number.


Example: array[5] = { 2,3,4,6,7 }; missing number is 5.


Time Complexity: O(log n)



int missing_number(int *a, int len)
{
    int mid = len / 2;


    if (len == 1) {
        printf ("missing number is %d\n", a[0] + 1);
        return (a[0] + 1);
    }


    if ((a[0] + mid) == a[mid])
    {
        // first half of array is not missing a number
        missing_number(&a[mid], len - mid);
    } else {
        // second half of array is not missing a number
        missing_number(a, mid);
    }
}