Lowest Common Ancestor

Problem Statment

Given a root of the binary tree and nodes n1 and n2. Find the lowest common ancestor of the nodes.

Example:
The lowest common ancestor for D and E in the above tree is C. The least common ancestor for D and B is A.

Lowest common ancestor with parent pointer
This problem is easily solved if parent pointer is given. All you need is to count distance to the root for both the nodes. If the distance for node n1 is l1 and node n2 is l2, find the larger of l1 and l2 and move the corresponding node up the tree by that distance. Once that is done, then we just need to move both the nodes up the tree one step at a time and check if the parent node is same. If it is then we have the common ancestor.

Here is the code:

Node *lca_parent(Node *n1, Node *n2) {

        Node *t1 = n1, *t2 = n2;

        int c1 = 0, c2 =0;

        // Find the distance to the root for n1
        while(t1 != NULL) {
            t1 = t1->parent;
            c1++;
        }

        // Find the distance to the root for n2
        while(t2 != NULL) {
            t2 = t2->parent;
            c2++;
        }

        // Move up the tree for the node that is
        // furthest from the tree
        if (c1 < c2) {
            while(c1 < c2) {
                n2 = n2->parent;
                c1++;
            }
        } else {
            while (c2 parent;
                c2++;
            }
        }

        // Keep pn moving up the tree  for both nodes
        // n1 and n2 until we have the same parent.
        while (n1 != n2) {
            n1 = n1->parent;
            n2 = n2->parent;
        }

        return n1;
}

Lowest common ancestor without parent pointer
If parent pointer is not given we can find lowest common ancestor by searching the nodes in the tree. We can use post order traversal and keep track if we have seen the node in the current subtree. Once we have seen the node in both subtrees or the current node is one of the node and the other node has been found in one of this node's subtree then we are done. The code is given below:

/*
 * Find lowest common ancestor
 * @param root - root of the tree
 * @param n1 - one of the node whose ancestor is to be determined 
 * @param n2 - the other node whose ancestor is to be determined
 * @param result - the lowest common ancestor
 */
bool lca(Node* root, Node *n1, Node *n2, Node **result) {

    if (root == NULL)
        return false;

    bool l = lca(root->left, n1, n2, result);
    bool r = lca(root->right, n1, n2, result);

    bool res = true;
    if (l && r) {
        *result = root;
    } else if((root == n1 || root == n2) && (l || r)) {
        *result = root;
    } else if (root != n1 && root != n2) {
        res = false;
    }
    
    return res || l || r;
}

Find subset of two or three numbers in a sorted array that sum upto a given value

Problem Statement

Given a number and a sorted array print all possible subsets containing two numbers that sum unto the given number.

Example 1:  array: [-3, -2, -1, 0, 1, 2,  3, 4,  5, 6, 7],  sum: 0
The 2-subsets are [-3, 3], [-2, 2] and [-1 , 1]

Example 2:  array: [1, 3, 4, 5, 6, 7],  sum: 6
The 2-subsets is [1, 5]

This is an instance of well known subset sum problem. But it's not as hard as we just need to produce subsets of 2 numbers. The idea here is to maintain two pointers, one starting from the left (lb) and the other starting from the right (ub). If the sum of x[lb] and x[ub] equals to the sum, we have identified the first subset. If it  is smaller than the sum, then move lb to the right otherwise move ub to the left. Keep on doing this until lb meets ub.

This problem is pretty straightforward and a working solution is given below:

void sum2(int x[], int n, int sum) {

    int lb = 0;
    int ub = n - 1;

    while(lb < ub) {

        if (x[lb] + x[ub] > sum) {
            ub--;
        } else if(x[lb] + x[ub] < sum) {
            lb++;
        } else  {
            std::cout << x[lb] << ", " << x[ub] << std::endl;
            lb++;
            ub--;
        }
    }
}

This solution can easily be extended to 3-subset. All we need is to find subset of two elements for each element in the array. The solution is given below:

void sum3(int x[], int n, int sum) {

    int lb = 0;
    int ub = n - 1;

    for (int i = 0; i < n; i++) {

        int lb = i + 1;
        int ub = n - 1;
        int num = sum - x[i];

        while(lb < ub) {

            if (x[lb] + x[ub] > num) {
                ub--;
            } else if(x[lb] + x[ub] < num) {
                lb++;
            } else  {
                std::cout << x[i] << ", " << x[lb] << ", " << x[ub] << std::endl;
                lb++;
                ub--;
            }
        }
    }
}

Find first missing number in an array containing consecutive numbers

Given a sorted array with no duplicates find the first number that is missing in the sequence.
For an input array where no number is missing, return 1 + largest element in the array.

Example 1: [1, 2, 3, 4, 7] 
The first missing number is 5.

Example 2: [-1, 0, 1, 2, 3, 4, 5, 6, 7, 9] 
The first missing number is 8.

Example 3: [1, 2, 3, 4, 5, 6] 
There is no missing number. So return 7.

We are aware of binary search technique to find a number in sorted array. But is there a way to extend it to find the missing number? The idea here is to locate the first missing index and we can do that using binary search. A number is missing in the left for an array x, if x[0] + index < x[index], otherwise it's missing in the right. The binary search will eventually lead to to consecutive indices where the number is missing or to the end of the array. In the latter case the result is the largest number in the array + 1.

int find_first_missing_number(int x[], int n) {

    int a = x[0];
    int lb = 0;
    int ub = n - 1;

    // Narrow down the range where the number may be located
    while(ub - lb > 1) {
        int mid = lb +(ub-lb)/2;

        if (x[mid] == a + mid) {
            lb = mid;
        } else if (x[mid] > a + mid) {
            ub = mid;
        }
    }

    // At this point lb + 1 should be equal to ub and
    // if the number NOT missing then x[lb] + 1 should be 
    // equal to x[ub]
    // if the number is missing then x[lb] + 1 is the first
    // missing number
    if (x[lb] + 1 == x[ub])
        return x[ub] + 1;

    return x[lb] + 1;
}