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.

Binary tree reconstruction from IN and PRE or POST order traversals

Reconstructing binary tree from Inorder and Preorder traversal is pretty straighforward. The idea is to number the Inorder sequence in increasing order and use that number as a key to insert into Binary Search Tree. The insertion into BST is carried out in the order given in Preorder traversal.

Example:
Inorder: DBEAFCG
Preorder: ABDECFG

Now number the inorder traversal:DBEAFCG (1234567). Thus the preorder traversal will be ABDECFG (4213657)

Insert the items picking them in preorder into BST. So first you will insert 4(A), then 2(B), 1(D) and so on. This will give you the original tree from which traversals are generated.

Code for it is given below

//Tree node
class Node {

public Node left;
public Node right;

//key
public int key;

//label of the node
public char label;

public Node(Node left, Node right, int key, char label){
this.left = left;
this.right = right;
this.value = val;
this.key= key;
}


public Node(int key, char label) {
this(null, null, key,label);
}


}

//Binary Search Tree
class Tree {
public Node root;

public Tree() {
this(null);
}
public Tree(Node root) {
this.root = root;
}


public void insert(int key, char label) {

Node node = new Node(key, label);
if(root == null) {
root = node;
return;
}

Node temp = root;
Node parent = root;

while(temp != null) {
parent = temp;
if ( key < temp =" temp.left;" temp ="=" left =" node;" temp =" temp.right;" temp ="=" right =" node;" table =" new" count =" 0;" bst =" new">

Reconstruction from Inorder and Postorder

Steps are pretty much the same for Postorder too. But while inserting into BST we start from last element of the traversal and continue on to first.