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

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

Tree Problems

Many of the tree problems asked in the interviews can be solved by extending traversal algorithms. There are 4 popular ways a tree can be traversed. They are preorder traversal, post order traversal, inorder and level order traversal. We will look at each of these traversals and some sample interview questions that can be answered using the given traversal.

Preorder Traversal

In preorder traversal you start from root, visit left child first and then right child. The processing for that node is done before processing it's children.

void pre_order(Node *root) {
    if (!root) {
        return;
    }
    // Process the node
    std::cout << root->name << std::endl;

    // Traverse left and right children
    pre_order(root->left);
    pre_order(root->right);
}

Sample Interview Problems:

Given a binary tree, serialize and deserialize it.

Given a root and a node in a binary tree, find the path from the root to the node.

Post Order Traversal
In post order traversal you start from root, visit left child first and then right child. The processing for the node is done after processing it's children.

void post_order(Node *root) {
    if (!root) {
        return;
    }

    // Traverse left and right children
    post_order(root->left);
    post_order(root->right);

    // Process the node.
    std::cout << root->name << std::endl;
}

Sample Interview Problems:
Given a binary tree create an in place mirror image of the tree.
Expression evaluation.

In Order Traversal
In in-order traversal you start from root, visit left subtree first and then right subtree. The processing for the node is done before you start traversing right subtree.

void in_order(Node *root) {
    if (!root) {
        return;
    }

    // Traverse left child
    post_order(root->left);

    // Process the node
    std::cout << root->name << std::end;

    // Traverse right child
    post_order(root->right);
}

Sample Interview Problems:
Convert a binary search tree into doubly linked list.

Level Order Traversal
In level-order traversal you start from root, process the root and then move to next level. In the next level you process all the nodes from left to right and then move to next level and so on.

#include <queue>
#include <iostream>
void level_order(Node *node) {
    if (!node)
        return;

    std::queue queue;

    // Count of the nodes in current level
    int cur_count = 0; 

    // Count of the nodes in the next level
    int child_count = 0; 

    queue.push(node);

    // Start with 1 as we have root in the queue
    // to begin with
    cur_count += 1;

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

        // Process the node. We will just print to 
        // indicate processing.
        std::cout << n->name << " ";
        
        // Decrement of the count of nodes remaining in the
        // queue  for current level.
        cur_count--;

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

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

        // When we hit a count of 0, we start at next level
        if (cur_count == 0) {
            cur_count = child_count;
            child_count = 0;
            std::cout << std::endl;
        }
    }
}

Sample Interview Problems:
Pretty print a binary tree.
Given a binary tree, return each level as a list.
You have a binary tree.  Lets say you add an extra sibling pointer to it. Can you fill all the sibling pointers to point to it's sibling starting  from the left to the right.


I will add more sample problems as well as provide solutions to as many I can.

Iterative Inorder Traversal

Iterative inorder traversal is a little complicated than Preorder traversal. As for Preorder we need to use stack for Inorder traversal as well but the nodes can't be removed from stack until it's children are pushed to the stack and the node has been visited. For all nodes we need to push their children on the stack first before visiting it. We mark whether the children have been put into stack or not for a node my using another stack call marks. When adding children to the stack we set mark to true on the marks stack. Now when we pop the node again we check corresponding mark and if it is set to true we know that it's children has already been processed. Thus we visit the node (print the value in the code below). In Inorder traversal left child, parent and right child are processed respectively. So while pushing on the stack we do it on the reverse order so that Inorder requirements are maintained.

  
void inorder_traversal(Node *root) {
 if(root == 0)
  return;

 std::vector<bool> marks;
 std::vector<Node*>nodes;
 nodes.push_back(root);
 marks.push_back(false);

 while(!nodes.empty()){

//read the top mark
  bool mark = marks.back();
  marks.pop_back();

 //read the top node
  Node *node = nodes.back();
  nodes.pop_back();
 
 if(mark) {
 //if mark is set then the node is visited
   std::cout << node->value_ << std::endl;
  }
  else {
 //put the righ child on stack
   if(node->right_ != NULL) {
    nodes.push_back(node->right_);
    marks.push_back(false);
   }

 //set mark to true
 //put the node in the stack
   marks.push_back(true);
   nodes.push_back(node);

 //put left child on the stack
   if(node->left_ != NULL) {
    nodes.push_back(node->left_);
    marks.push_back(false);
   }
  }
 }
}
 

Converting BST to sorted Doubly Linked List

Today, one of my friend asked how to convert a Binary Search Tree to sorted Doubly Linked List. He came across this problem while preparing for interview. I then began to dig what I could remember about BST. I had learnt from my Data Structures course in college that most tree problems boil down to tree traversal problems. So I started thinking along that line and suddenly came out with a solution. The idea is to traverse the tree In Order and adjust the pointers accordingly. The code for this is pretty straight forward.

Node *last_left = 0;

void traverse(Node * node)
{
 if(node == 0)
   return;
 //traverse left tree
 traverse(node->left_);

 //adjust the left and right pointers (left points to previous
//and right points to next)
 //in terms of doubly linked list
 if(last_left != 0){
   last_left->right_ = node;
   node ->left_ = last_left;
   last_left = node;
 }
 else
   last_left = node;

 //traverse right subtree
 traverse(node->right_);
}