Binary Search Tree : Build binary search tree given inorder and preorder traversal

Introduction : Binary Search Tree

Basic definition and problems related to binary search tree can be read at this post.

Today's problem statement is 
Given in-order and pre-order traversal of a binary search tree, build the binary search tree.
For example,
In-order traversal is {10, 12, 20, 30, 37, 40, 45}
Pre-order traversal is {30, 20, 10, 12, 40, 37, 45}

The resultant binary search tree should be

Analysis

As we know that inorder traversal of a BST list left child first, then root and right child last.
Preorder traverses root first, left node and at last right node.

Can we use these properties?

First step, find the root of the tree. Going by the property of preorder traversal, first element will be the root of the tree. 
So, we have root with us.

Search for the element in inorder traversal. According to inorder traversal, all elements on the left side of the root element will form left sub tree, and all on right side will form right sub tree.

Cool, we have now root node of BST, left sub tree and right sub tree.

Now we need to find the root of left sub tree and right sub tree and add them to the root.

Again, after root, next element will be root of either left sub tree or right sub tree. We can do this by looking into the two sub parts of inorder traversal.

From above discussion, we can see that at every step, we divide the inorder traversal in two parts and use preorder traversal to search for root of sub trees.

Algorithm

1. Take first element in preorder traversal and make root.
2. Search for the element in step 1 in inorder traversal.
3. Take left part of inorder traversal and repeat step 1 and 2 with next element in preorder traversal as root.
4. Take right part of inorder traversal and repeat step 1 and 2 with next element in preorder traversal as root.

* This algorithm will automatically take care when there is no element in left or right sub tree.

Code

Node * create_tree(int inorder[], int preorder[],
                      int startIndex, int endIndex){

   static int preIndex =0;
   int i =0;

   if(startIndex > endIndex)
         return NULL;
   Node * temp =  (Node *)malloc(sizeof(Node));

   if(temp){
       /* Take next preorder element and peg it as root */

       temp->value = preorder[preIndex++];

      if(startIndex == endIndex) return temp ;
      
      /* Search for the element in inorder traversal */
      int index = search_inorder(inorder,temp->value,
                                  startIndex, endIndex);

       /*All elements in left side form left sub tree */
       temp->left = create_tree(inorder, preorder,  
                                startIndex, index-1 );
        /*All elements in right side form right sub tree */
        temp->right  = create_tree(inorder, preorder, 
                                    index+1, endIndex );

       return temp;
    }
    return NULL;

}

int search_inorder(int inorder[], int elem, int start, int end){

        int i;

        for(i=start;i<=end; i++){

                if(inorder[i]== elem)

                        return i;

        }

        return -1;

}

Above code executes as follows

Root : 30
Left sub tree :10, 12, 20 
Right sub tree :37, 40, 45

Root : 20
Left sub tree :10, 12 
Right sub tree :

Root : 10
Left sub tree :
Right sub tree :12

Root : 40
Left sub tree : 37 
Right sub tree : 45 

Final output will be

10, 12, 20, 30, 37, 40, 45

Test cases

1. Normal tree

In-order traversal  {10, 12, 20, 30, 37, 40, 45}
Pre-order traversal {30, 20, 10, 12, 40, 37, 45}

2. Empty tree
In-order traversal  :{}
Pre-order traversal :{}

3. When inorder or preorder does not form BST
Fail

4. When tree has duplicate elements

Complexity Analysis

Complexity of above algorithm is O(N*N) as for every element in preorder, we might need to traverse the whole inorder array if tree is completely skewed. 

References

http://www.geeksforgeeks.org/construct-tree-from-given-inorder-and-preorder-traversal/

http://www.youtube.com/watch?v=PAYG5WEC1Gs