I'm trying to construct a binary tree (unbalanced), given its traversals. I'm currently doing preorder + inorder but when I figure this out postorder will be no issue at all.

I realize there are some question on the topic already but none of them seemed to answer my question. I've got a recursive method that takes the Preorder and the Inorder of a binary tree to reconstruct it, but is for some reason failing to link the root node with the subsequent children.

Note: I don't want a solution. I've been trying to figure this out for a few hours now and even jotted down the recursion on paper and everything seems fine... so I must be missing something subtle. Here's the code:

    public static <T> BinaryNode<T> prePlusIn( T[] pre, T[] in)
{
    if(pre.length != in.length)
        throw new IllegalArgumentException();

    BinaryNode<T> base = new BinaryNode();
    base.element = pre[0]; // * Get root from the preorder traversal.
    int indexOfRoot = 0;

    if(pre.length == 0 && in.length == 0)
        return null;

    if(pre.length == 1 && in.length == 1 && pre[0].equals(in[0]))
        return base; // * If both arrays are of size 1, element is a leaf.

    for(int i = 0; i < in.length -1; i++){
        if(in[i].equals(base.element)){    // * Get the index of the root
            indexOfRoot = i; // in the inorder traversal.
            break;
        } // * If we cannot, the tree cannot be constructed as the traversals differ.
        else throw new IllegalArgumentException();
    }
    // * Now, we recursively set the left and right subtrees of 
    // the above "base" root node to whatever the new preorder
    // and inorder traversals end up constructing.

    T[] preleft = Arrays.copyOfRange(pre, 1, indexOfRoot + 1);
    T[] preright = Arrays.copyOfRange(pre, indexOfRoot + 1, pre.length);
    T[] inleft = Arrays.copyOfRange(in, 0, indexOfRoot);
    T[] inright = Arrays.copyOfRange(in, indexOfRoot + 1, in.length);

    base.left = prePlusIn( preleft, inleft); // * Construct left subtree.
    base.right = prePlusIn( preright, inright); // * Construc right subtree.

    return base; // * Return fully constructed tree
}

Basically, I construct additional arrays that house the pre- and inorder traversals of the left and right subtree (this seems terribly inefficient but I could not think of a better way with no helpers methods).

Any ideas would be quite appreciated.

Side note: While debugging it seems that the root note never receives the connections to the additional nodes (they remain null). From what I can see though, that should not happen...

EDIT: To clarify, the method is throwing the IllegalArgumentException @ line 21 (else branch of the for loop, which should only be thrown if the traversals contain different elements.