CareerCup

or even levelorder

We can construct a tree with inorder & levelorder...this is a standard google interview question. The solution is as follows.

/**
Consider for example
In-order: 3 2 1 4 5 7 6
Level-order: 4 2 7 3 1 5 6

root = levelorder[0]#set root to first element in levelorder
subIn1, subIn2 = partition(inorder, levelorder[0]) #partition inorder based on root
subLevel1 = extract(levelOrder, subIn1)#remove elements in level order not in subIn1
subLevel2 = extract(levelOrder, subIn2)#remove elements in level order not in subIn2
root->left = f(subIn1, subLevel1)
root->right = f(subIn2, subLevel2)
return root


*/
public static BTNode buildBTFromInOrderAndLevelOrder(Object[] inOrderData, Object[] levelOrderData){
if(inOrderData.length != levelOrderData.length){
System.out.println("Inconsistent data: No.of BTNodes in InOrder & LevelOrder don't match");
return null;
}
//the root node is the first element in the LevelOrder data
BTNode rootBTNode = new BTNode();
Object rootData = levelOrderData[0];
rootBTNode.setData(rootData);

//base condition
if(inOrderData.length == 1){
return rootBTNode;
}

int inOrderRootIndex = Arrays.binarySearch(inOrderData, rootData);
Object[] leftSubInOrderData = Arrays.copyOfRange(inOrderData, 0, inOrderRootIndex);
List levelOrderList = new ArrayList(Arrays.asList(levelOrderData));
levelOrderList.retainAll(Arrays.asList(leftSubInOrderData));
Object[] leftSubLevelOrderData = levelOrderList.toArray();

Object[] rightSubInOrderData = Arrays.copyOfRange(inOrderData, inOrderRootIndex+1, inOrderData.length);
levelOrderList = new ArrayList(Arrays.asList(levelOrderData));
levelOrderList.retainAll(Arrays.asList(rightSubInOrderData));
Object[] rightSubLevelOrderData = levelOrderList.toArray();

rootBTNode.setLeft(buildBTFromInOrderAndLevelOrder(leftSubInOrderData,leftSubLevelOrderData));
rootBTNode.setRight(buildBTFromInOrderAndLevelOrder(rightSubInOrderData,rightSubLevelOrderData));
//the tree is constructed now in a recursive way
return rootBTNode;
}