# Construct binary tree from inorder and preorder traversals

Given Inorder and Preorder traversals of a binary tree with no duplicate node values, how can you construct a binary tree which generates these traversal arrays?

For example, if we are given following two arrays -
inorder = [4,2,5,1,6,3,7] and preorder = [1,2,4,5,3,6,7] we need to construct following tree.

1
2             3
4    5        6     7

## Algorithm/Insights

Let us try to understand this algorithm using an example.
Say we are given following two arrays -
preorder = [1,2,4,5,3,6,7]
inorder = [4,2,5,1,6,3,7]

Now what we know is pre-order traversal visits tree in N-L-R fashion (N:node, L:left sub-tree, R:right sub-tree) and in-order traversal visits tree in L-N-R fashion. With this is mind, if we now look at the above preorder array, we can say that node '1' must be the root of the tree. Now for the tree with '1' as the root, we will try constructing left and right sub-trees. To find the nodes in left and right sub-trees we make use of the given in-order array. Because in-order traversal visits tree in L-N-R fashion, if we find the node '1' in the in-order array, all the elements to the left of element '1' in the in-order array will be in the left sub-tree and all the elements to the right of element '1' will be in the right sub-tree. Note that sub-arrays formed by elements which are to the left and to the right of '1' are also in-order traversals of left and right sub-tress of the tree with root as 1.

Basically, we need to construct left sub-tree of '1' using inorder array [4,2,5] and we need to construct right sub-tree of '1' using inorder array [6,3,7].
Coming back to the fact that in the pre-order traversal left sub-tree is visited(before right sub-tree visit) after node is visited and by knowing the number of nodes in the left sub-tree using inorder array [4,2,5] which has all the nodes in left sub-tree of '1', we can now divide the remaining pre-order array that is  [2,4,5,3,6,7] in left sub-tree nodes and right sub-tree nodes (for root '1'). Since size of array [4,2,5] is 3, pre-order array for left sub-tree would be [2,4,5] and since size of right sub-tree is also 3 pre-order array for right sub-tree would be [3,6,7].

To summarize, our problem is now reduced to constructing a tree with node '1' as the root with its left sub-tree having in-order array as [4,2,5] and pre-order array as [2,4,5]; and its right sub-tree having in-order array as [6,3,7] and pre-order array as [3,6,7]. Notice that problems of constructing right and left sub-trees have similar problem definitions as the original problem but with reduced array sizes. In other words, we need to use recursion to solve the original problem. The base case for this recursive problem would be that if the arrays are empty we will return null tree.

The steps of this recursive algorithm are as following -
1. Call createTree(inorderArray = inorder,lowInorder = 0,highInorder = inorder.length-1,preorderArray = preorder,lowPreorder = 0, highPreorder = preorder.length - 1)
2. If (lowInorder > highIorder) or (lowPreorder > highPreorder) then we know that we have hit the base case and we return null tree.
3. Else,
3a. We create a root with value as preorder[lowPreorder]
3b. We find out the index of this root(preorder[lowPreorder]) in inorder array. Let's call this index divideIndex.
* All the elements in the in-order array starting from the lowInorder index up to and excluding divideIndex are in left sub-tree and all the elements in the in-order array starting from the divideIndex+1 up to and including highInorder index are in the right sub-tree.
3c. Using the size of left sub-tree and right sub-tree we find out the correct indices in the pre-order array for left sub-tree and the right sub-tree. Using these indices we make a recursive call, where we set

root.left = createTree(inorder, lowInorder, divideIndex - 1,preorder, lowPreorder+1, lowPreorder+sizeOfLeftSubTree);

and

root.right = createTree(inorder, divideIndex + 1, highInorder, preorder, lowPreorder+sizeOfLeftSubTree+1, lowPreorder+sizeOfLeftSubTree+sizeOfRightSubTree);

4. After the recursive steps in step 3, our tree is completely constructed and we return root to the calling function.

Worst case time complexity of this algorithm  is O(n^2) when the tree that needs to be constructed is skewed as shown below.

1
2
3
4

This recursive algorithm is implemented in the createTree function below. Please checkout code and algorithm visualization section for more details of the algorithm.

## Code Snippet

```
package com.ideserve.questions.nilesh;

/**
* <b>IDeserve <br>
* Given Inorder and Preorder traversals of a binary tree with no duplicate node values,
* how can you construct a binary tree which generates these traversal arrays?
* @author Nilesh
*/

public class ConstructBinaryTreeFromInorderAndPreorder {
class TreeNode
{
TreeNode left;
TreeNode right;
int val;

public TreeNode(int x)
{
this.val = x;
}
}

int searchInorder(int val, int[] inorder, int lowInorder, int highInorder)
{
for (int i = lowInorder; i <= highInorder; i++)
{
if (val == inorder[i]) return i;
}
return -1;
}

TreeNode createTree(int[] inorder, int lowInorder, int highInorder, int[] preorder, int lowPreorder, int highPreorder)
{

if ((lowInorder > highInorder) || (lowPreorder > highPreorder)) return null;

TreeNode root = new TreeNode(preorder[lowPreorder]);

int divideIndex = searchInorder(root.val, inorder, lowInorder, highInorder);

int sizeOfLeftSubTree = divideIndex - lowInorder;
int sizeOfRightSubTree = highInorder - divideIndex;

root.right = createTree(inorder, divideIndex + 1, highInorder,
preorder, lowPreorder+sizeOfLeftSubTree+1, lowPreorder+sizeOfLeftSubTree+sizeOfRightSubTree );

root.left = createTree(inorder, lowInorder, divideIndex - 1,
preorder, lowPreorder+1, lowPreorder+sizeOfLeftSubTree);

return root;
}

public TreeNode buildTree(int[] preorder, int[] inorder) {
return createTree(inorder, 0, inorder.length - 1, preorder, 0, preorder.length - 1);
}

private void printInorder(TreeNode root)
{
if (root == null) return;

printInorder(root.left);
System.out.print(" "+ root.val + ",");
printInorder(root.right);
}

private void printPreorder(TreeNode root)
{
if (root == null) return;

System.out.print(" "+ root.val + ",");
printPreorder(root.left);
printPreorder(root.right);
}

public static void main(String[] args)
{
ConstructBinaryTreeFromInorderAndPreorder solution = new ConstructBinaryTreeFromInorderAndPreorder();

/*
1
2            3
4   5        6    7
*/

int[] inorder = {4,2,5,1,6,3,7};

int[] preorder = {1,2,4,5,3,6,7};

TreeNode root = solution.buildTree(preorder, inorder);
System.out.print("Inorder array for re-constructed tree is:");
solution.printInorder(root);

System.out.println("");

System.out.print("Preorder array for re-constructed tree is:");
solution.printPreorder(root);
}
}
```

## Order of the Algorithm

Time Complexity is O(n^2)
Space Complexity is O(1)