Construct Binary tree from given inorder and pre-order traversal of Binary Tree.

/*
        1. Scan pre-order from left to right and search the encountered node in given in-order array.
        2. Store position of element in pos.
        3. Construct node having value inorder[pos].
        4. Divide inorder in left (start, pos-1) and right (pos+1,end).

preOrder = {50,30,20,40,35,45,70,60,80};
inOrder =  {20,30,35,40,45,50,60,70,80};


1. 50

50
20,30,35,40,45 60,70,80


2. 30
50
30 60,70,80
20 35,40,45

3. 20 (Return node as start = end.

4. 40
50
30 60,70,80
20 40
35 45

5. 35 (start = end)
6. 45 (start = end)
7. 70 (start = end)
50
30 70
20 40 60 80
35 45
8. 60 (start = end)
9. 80 (start = end)

*/
private int[] preOrder = {50,30,20,40,35,45,70,60,80};
private int[] inOrder =  {20,30,35,40,45,50,60,70,80};
private int prePos = 0;


public int searchInOrder(int s , int e , int n)
{
for(int i =s ; i <= e; i++)
{
if(inOrder[i] == n)
return i;
}
return -1;
}


public BSTNode createTree(int start, int end)
{
if(prePos >= preOrder.length)
return null;

BSTNode newNode = new BSTNode();
newNode.setData(preOrder[prePos++]);

if(start == end)
{
return newNode;
}

int pos = searchInOrder(start,end,newNode.getData());
newNode.setLeftChild(createTree(start, pos-1));
newNode.setRightChild(createTree(pos+1, end));

return newNode;
}


public void buildTree()
{
prePos = 0;
root = createTree(0,preOrder.length-1);
}


BST tree = new BST();
tree.buildTree();