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.