Constructing a Binary Tree from its traversals
- by user991710
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.
