Constructing a Binary Tree from its traversals

Question

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 = -1 ;

    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(pre[0])){    // * 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.

        if (indexOfRoot == -1) 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.

EDIT2: Figured this out thanks to a helpful post from @Philip (coincidentally, we have the same first name... fun!). However, if anyone happens to have any advice on improving efficiency, I would appreciate the input.

Answer 1

this code is very suspicious to me

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();
}

You enter the loop and i is set to 0, if i is less than in.length - 1 you evaluate the body of the loop which is an if expresion. At this point one of two things will happen

1. in[i] equals base.element in which case indexOfRoot will be set to 0 and you will break out of the loop
2. You throw an exception

Either way you never actually increment i

Try to rework this loop to do what you want, since it definitely isn't doing what you want now. You might try something like

int indexOfRoot = -1; //an impossible value
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(indexOfRoot == -1){//if the root was never set
    throw new IllegalArgumentException();
}

although that is still kinda ugly (for one thing, base.element never changes, so you might want to use pre[0] for clarity). And, by no means am I sure it is fully correct. Still, it is probably closer to what you want