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

Find first index of a number in the sorted array containing duplicates

This can be done easily in linear time by making a pass through the array. In coding interviews it is not likely the solution the interviewer is looking for. So we have to do better. We know that binary search provides a efficient solution for finding an element in sorted array. Lets look at the problem to see if we can modify the binary search algorithm to solve this problem. We can start with binary search to find the index. Once we find the index we have to look to the left to check if the number is present. If we look to the left linearly then the solution will be O(n). To do better than that we can use another binary search in the left and continue until we find the fist index where the number occurs.

/**
 * Find first index of the number k in the sorted
 * array x of size n
 */
int first_index(int x[], int n, int k) {
    int lo = 0;
    int hi = n - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo)/2;

        if (x[mid] == k) {
            if (mid > 0 && x[mid - 1] == k) {
                hi = mid - 1;
            } else {
                return mid;
            }

        } else if(x[mid] < k) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }

    return -1;
}

Iterative inorder traversal of a binary tree using constant space.

In order traversal of a binary tree can be performed using O(1) storage if the tree stores parent pointer. The trick is to look at possible directions we need to move in the tree.  As shown in the diagram below there are 3 directions that you can move in a binary tree. They are to the left, right or up. Given this all we need is to establish conditions that decides the movement. Consider last visited node as the node we were in before coming to the current node. Here are the cases:

1. If the last visited node is the parent node and the current node's left child exists move left.

2. If the last visited node is the left child of the current node and the current node has right child move right.

3. If the last visited node is on the left or right move up.

For the node to be the next successor for inorder traversal one of the following conditions should hold ( We will print the node value in our sample code below whenever this condition holds):

1. The last visited node was the left child.

2.  The left child of the current node doesn't exist.

It's now easy to translate these conditions into code. All you need is these conditions and some additional null checks as shown in the code below.

void inorder_constant_space(Node *root) {

    if (!root)
        return;

    Node *last = NULL;
    Node *node = root;

    while (node) {

        if (last == node->left || 
                (last == node->parent && node->left == NULL)) {
            std::cout << node->name;
        }

        if (last == node->left && node->right != NULL) {
            last = node;
            node = node->right;
        } else if(last == node->left) {
            last = node;
            node = node->parent;
        } else if (last == node->parent && node->left == NULL
                         && node->right != NULL) {
            last = node;
            node = node->right;
        } else if (last == node->parent && node->left == NULL) {
            last = node;
            node = node->parent;
        } else if (last == node->parent) {
            last = node;
            node = node->left;
        } else {
            last = node;
            node = node->parent;
        }
       
    }
}

Fill in the sibling pointer in the binary tree

You are given a binary tree which has a sibling pointer in addition to left and right pointer. The tree has left and right child set correctly but sibling pointer is not yet set. Your task is to traverse the tree and fill in the sibling pointer. A sibling is defined as a node next to the given node at the same level.

In the tree above B and C, and D and E are siblings. So sibling pointer of B should point to C and sibling pointer of D should point to E. Sibling pointer of C and E should be null because they don't have any siblings to the right.

This problem is easily solved using level order traversal as shown below.

class Node {
public:
    Node *left;
    Node *right;

    // Sibling pointer that needs to be set
    Node *sibling;

    // Value stored in the node. For simplicity

    // we assume name to be the value
    std::string name;
};

// Fill in the sibling pointer of a binary tree
void fill_node_with_next_sbiling(Node *node) {
    if (!node)
        return;

    // Initialize the queue with the root node.
    std::queue<node> queue;
    queue.push(node);

    // Set count of current level in the queue to 1.
    int cur_count = 1;
    int child_count = 0;

    Node *prev = NULL;

    while (!queue.empty()) {
        Node *n = queue.front();
        queue.pop();

        // Set the sibling pointer and set previous as current node
        if (prev) {
            prev->sibling = n;
            prev = n;
        } else {
            prev = n;
        }

        cur_count--;

        if (n->left != NULL) {
            queue.push(n->left);
            child_count++;
        }

        if (n->right != NULL) {
            queue.push(n->right);
            child_count++;
        }

        // All nodes in the current level are done.
        // Set the cur_count to next level count 
        // for processing next level
        if (cur_count == 0) {
            cur_count = child_count;
            child_count = 0;
            prev = NULL;
        }

    }
}

Convert a binary search tree into doubly linked list

Converting a binary search tree into doubly linked list is a common interview question. It's a simple question as long as we know it can be solved by extending inorder tree traversal. If you are not familiar with inorder tree traversal, I have described it here. In this problem you are given a binary search tree with left and right child and you are supposed to convert left pointer to predecessor node and right pointer to the successor node. Here is the solution to the problem:

// output list
Node *list = NULL;

void convert_to_doubly_ll(Node *root) {
    if (root == NULL)
        return;

    convert_to_doubly_ll(root->left);

    if (list) {
        list->right = root;
        root->left = list;
    } 
    
    list = root;
    
    Node *right = root->right;
    root->right = NULL;

    convert_to_doubly_ll(right);
}

If you want to do this in place, then all you have to do is pass in the previous node in each recursive call. The code is given below:

void convert_to_doubly_ll_in_place(Node *root, Node **prev) {
    if (root == NULL)
        return;

    convert_to_doubly_ll_in_place(root->left, prev);

    Node *prev_node = *prev;
    Node *right = NULL;

    if (prev_node) {
        prev_node->right = root;
        root->left = prev_node;
    } 
    
    *prev = root;
    
    right = root->right;
    root->right = NULL;

    convert_to_doubly_ll_in_place(right, prev);
}

You can call the above method like this:

Node *root = ....a tree...;
Node *prev=NULL;
convert_to_doubly_ll_in_place(root, &prev);