restoreBinaryTree

Problem Statement: Given the inorder and preorder traversals of a binary tree t, but not t itself, restore t and return it.

We can start by taking the first element of preorder array and set it as root, and then we can recursively make its left and right child.

//
// Binary trees are already defined with this interface:
// class Tree<T> {
//   Tree(T x) {
//     value = x;
//   }
//   T value;
//   Tree<T> left;
//   Tree<T> right;
// }
int preOrderIndex;
HashMap<Integer, Integer> hmap;
Tree<Integer> solution(int[] inorder, int[] preorder) {

    hmap = new HashMap<>();
    for(int i=0; i<inorder.length; i++) {
        hmap.put(inorder[i],i);
    }

    preOrderIndex = 0;
    return buildTree(preorder, inorder, 0, inorder.length-1);

}

Tree<Integer> buildTree(int[] preorder, int[] inorder, int left, int right) {

    if(left>right || preOrderIndex>=preorder.length)
    return null;

    int val = preorder[preOrderIndex];
    Tree root = new Tree(val);

    preOrderIndex++;

    root.left = buildTree(preorder, inorder, left, hmap.get(val)-1);
    root.right = buildTree(preorder, inorder, hmap.get(val)+1, right);

    return root;
}

Note: For inorder and (pre/postorder) traversals - the idea is same, we will get the root element from preorder or postorder array and keep dividing the inorder array based on this.