// idxMap is the hash_table that maps each node in the
    // in-order array to its index in in-order array. e.g.
    // <key = 10, value = 3>
    // Recursion function returns the sub-tree root.
    public TreeNode construct(int[] in, int inLeft, int inRight, int[] pre, int preLeft, int preRight,
            Map<Integer, Integer> idxMap) {
        if (inLeft > inRight) {
            return null;// base case
        }

        TreeNode root = new TreeNode(pre[preLeft]);
        int leftSize = idxMap.get(root.key) - inLeft; // calculate left-subtree
                                                        // size
        root.left = construct(in, inLeft, inLeft + leftSize - 1, pre, preLeft + 1, preLeft + leftSize, idxMap);
        root.right = construct(in, inLeft + leftSize + 1, inRight, pre, preLeft + leftSize + 1, preRight, idxMap);
        return root;
    }