Construct binary tree from inorder and preorder traversal

Construct binary tree from inorder and preorder traversal

Given two traversals (inorder and preorder) of a binary search tree, Construct binary tree from inorder and preorder traversal For example,Inorder traversal is {10, 12, 20, 30, 37, 40, 45} and Preorder traversal is {30, 20, 10, 12, 40, 37, 45}; the resultant binary search tree should be as shown below

Construct binary tree from inorder and preorder traversal

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

First of all, understand that at least two traversals of tree are required to create a unique tree from given nodes. Else there are many possible combinations to create a binary search tree from given n nodes. To understand further how that is possible, please go through this post : Number of trees with N nodes.

Coming back to problem at hand: In inorder traversal of binary search tree list, left child is visited first, then root and right child visited last.Preorder traversal of BST traverses root first, left node and at last right node.Can we use these properties of two traversals to build an unique tree?

To build a tree, first step would be to find root of tree. As per the preorder traversal definition, first node which is traversed or visited will be root of the tree. So, first node of preorder traversal is root of resultant BST.  Now what nodes constitute its left and right sub trees? By inorder traversal definition, it is clear that root is visited once all nodes on left subtree are visited. Search for node which was selected as root from preorder traversal in inorder traversal. All the nodes on left side of root node in inorder traversal will form left sub tree, and all on right side of it will form right sub tree of resultant tree. Cool, we have root node of BST, left sub tree and right sub tree.Now, we need to find the roots of left sub tree and right sub tree and add them to root.

There are two possible scenarios with next node of root node, next node in preorder traversal can be left child of selected root or it can be right child of the root if the left sub tree of the root is NULL. How do we figure that out if the node is left child or right child is the question?

To see if there is a left subtree of given root, look into two sub parts of inorder traversal and see in which part next node of preorder traversal falls in inorder traversal. If it is on the left of root, then add it as left child of root else add it as right child of root.

Next step is how to create left and right sub trees? Its simple, repeat same process on left side and right side of root node in inorder traversal. At each step, divide inorder traversal in two parts and use preorder traversal to search for root of sub trees. Typical case of divide and conquer strategy.

Algorithm to construct binary tree from preorder and inorder traversal

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.

construct binary tree from preorder and inorder traversal : Implementation

#include <stdio.h>
 
typedef struct Node{
	int value;
	struct Node *left;
	struct Node *right;
}Node;
 
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 element, int start, int end){
 
	int i;
	for(i=start;i<=end; i++){
		if(inorder[i]== element)
			return i;
	}
	return -1;
}

void inorderTraversal(Node * root){
	if(root){
		inorderTraversal(root->left);
		printf("%d ", root->value);
		inorderTraversal(root->right);
	}
}
int main(void) {
	int inorder[] = {10, 12, 20, 30, 37, 40, 45};
	int preorder[] = {30, 20, 10, 12, 40, 37, 45};

	Node * tree = create_tree(inorder, preorder, 0, 6);

	inorderTraversal(tree);
	return 0;
}

Let’s take above example and see how this algorithm to build a binary search tree from inorder and preorder traversal works
build binary search tree from inorder and preorder traversal
Inorder  = {10, 12, 20, 30, 37, 40, 45} and preorder =  {30, 20, 10, 12, 40, 37, 45}

We take first node from preorder traversal and make it as root. So, root of resultant tree is : 30

Search for the node 30 in inorder traversal, it is at position 3 (zero based indexing). Left sub tree is formed by nodes from index zero to index 2 and right sub tree is formed by index 4 to index 6.

Left sub tree :10, 12, 20 and Right sub tree :37, 40, 45                        (1)

Now, we will first try to create left subtree of node 30. Are there elements in left sub tree? Yes, so next step is to find root among those elements. We will take next node from the preorder, that is 20 and allocate a node with value 20. Now, find node 20 in left sub tree part of inorder traversal that is from index 0 to index 2, we find it at index 2, so elements from 0 to 1 form left sub tree and there is no right subtree as inorder traversal was till  index 2 only. Hope this is clear. So root of left sub tree is : 20. Left tree and right sub tree for root 20 will be

Left sub tree :10, 12  and Right sub tree : NULL                                    (2)

Again we will try to create left sub tree of node 20 first. Are there elements in left sub tree? Yes, So next question is what is the root of the sub tree. Check preorder traversal. Next node in the preorder traversal is node 10, hence root will be 10, allocate and node and assign value as 10. Again nodes on left side of 10 are part of left subtree of root 10 and nodes on right are part of right sub tree of tree rooted at 10.

 Left sub tree : NULL and  Right sub tree :12                                       (3)

Is there anything on the left sub tree of 10? No. We are done with left part of node 10. Next we need to handle right sub tree of 10. Is there any element there. Yes there is! We will repeat the same process on to right sub tree of 10. To find the root of right sub tree, we will see what is next element in preorder after 10. It is 12, so root will 12. Left and right child of 12 will be :

Left sub tree : NULL and right subtree : NULL                            (4)

Now since left and right subtree both are NULL, return. Left and right subtree of node 10 are created and attached. We go back and check node 20. Is there element in right sub tree of 20. No. Check (2). So we will return from there too.

From above discussion it is clear that if there is only one node in any sub tree, we just allocate and return, and of course when any subtree is empty, return.

Same process is followed for the right sub tree of node 30, Root : 40

Left sub tree :37 and  Right sub tree :45                                             (5)

As there is only one node on each side of node 40, nodes 37 and 45 will be created and attached to node 40 as left and right child receptively.
Test cases

1. Normal tree
Inorder traversal  {10, 12, 20, 30, 37, 40, 45}
Preorder traversal {30, 20, 10, 12, 40, 37, 45}

2. Empty tree
Inorder traversal  :{}
Preorder traversal :{}

3. When inorder or preorder does not form BST
Fail

4. When tree has duplicate elements

Complexity of algorithm to construct binary tree from two traversal inorder and preorder is O(n2) as for every element in preorder, we might need to traverse the whole inorder array if binary search tree is completely skewed.

References:
http://www.geeksforgeeks.org/construct-tree-from-given-inorder-and-preorder-traversal/
http://www.youtube.com/watch?v=PAYG5WEC1Gs

  • http://www.blogger.com/profile/10300811986076753563 DaeMoohn

    Preorder traversal is: 30 20 10 12 40 37 45

  • http://www.blogger.com/profile/07885594236543253450 Jitendra Sangar

    Oh thanks, I will make changes.
    Thanks for pointing out.

  • http://www.blogger.com/profile/10300811986076753563 DaeMoohn

    Also, note that it’s possible to build a bst up from the preorder OR postorder representation.

    For preorder, you just process the nodes as being read from a queue. For postorder, you read them from stack.

    • http://www.blogger.com/profile/07885594236543253450 Jitendra Sangar

      Totally agree. I will try and write code for that too.
      Btw, preorder was wrong due to following error
      void preorder(Node * node){
      if(node == NULL)
      return;
      else{
      printf(“%d, “,node->value);
      inorder(node->left); <<<<<<<<<
      inorder(node->right);<<<<<<<
      }
      }

      Standard copy paste error 🙂

  • vickey

    We can use binary search instead of linear search as inorder array will be sorted in any case then Complexity would be O(NlogN)

    • http://algorithmsandme.in/ Jitendra Sangar

      Agreed.

  • Pingback: Amazon interview Experience 1 | Algorithms and Me()

  • skumar

    is it possible without static variable & locally defined

    • http://algorithmsandme.com/ Jitendra Sangar

      we can do so, just pass it as parameter to recursive call, make sure you pass it as reference as we will need updated value from each function return.

  • skumar

    is it possible without static variable & locally defined