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

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

    }
}

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.