Build a binary Tree from inOrder and preOrder data in Java

Question

I've gone through this program a few times, but I can't really see the issue. Basically, it is supposed to reconstruct a binary tree from inOrder and preOrder traversal data (sent in as integer arrays) It's a binary tree of integers.

Here's the tree I'm using:

 234
 / \
 98 678
 / \ \
45 124 1789

preOrder is 234, 98, 45, 124, 678, 1789 inOrder is 45, 98, 124, 234, 678, 1789

The problem that comes up is with 1789. The code reconstructs the tree up to 1789, leaving it out for some odd reason. I decided to switch 678 and 1789 in the inOrder array, and that put 1789 to the left of 678, and a 0 to the right of 678. In the code below, the arrays are in the order they are supposed to be (or what I assume is supposed to be).

Build Tree code:

public class BuildTree
{
public static BinaryTreeNode buildTree(int inOrder[], int preOrder[], int preIndex )
{ 
 if (inOrder.length > 1) 
 {
 int inIndex = 0;
 for (int i = 0; i < inOrder.length; i++)
 {
 if (preOrder[preIndex] == inOrder[i])
 {
 inIndex = i ;
 break; 
 }
 }
 if (inIndex > 0)
 { 
 BinaryTreeNode node = new BinaryTreeNode(inOrder[inIndex]);
 if (preIndex < preOrder.length - 1 )
 {
 node.setLeft(buildTree(leftArray(inOrder, inIndex), preOrder, preIndex + 1));
 node.setRight(buildTree(rightArray(inOrder, inIndex), preOrder, inIndex + 1)); 
 }
 return node;
 } 
 } 
 return new BinaryTreeNode(inOrder[0]);
}
public static int[] leftArray(int[] input, int index)
{ 
 int left[] = new int [index];
 for (int i = 0 ; i < index ; i ++)
 {
 left[i] = input[i] ;
 }
 return left; 
}
public static int[] rightArray(int[] input, int index)
{ 
 int right[] = new int [index];
 int x= 0;
 for (int i = index +1 ; i < input.length ; i ++)
 {
 right[x] = input[i] ;
 ++x;
 }
 return right; 
}
} //end class

BinaryTreeNode:

public class BinaryTreeNode
{
 private int data;
 private BinaryTreeNode left;
 private BinaryTreeNode right;
 BinaryTreeNode()
 {
 }
 BinaryTreeNode(int data)
 {
 this.data = data;
 }
 public void setData(int data) {
 this.data = data;
 }
 public void setLeft(BinaryTreeNode left) {
 this.left = left;
 }
 public void setRight(BinaryTreeNode right) {
 this.right = right;
 }
 public int getData() {
 return data;
 }
 public BinaryTreeNode getLeft() {
 return left;
 }
 public BinaryTreeNode getRight() {
 return right;
 }
}

Main method for testing:

public static void main(String[] args)
{
 int[] preOrder = {234, 98, 45, 124, 678, 1789};
 int[] inOrder = {45, 98, 124, 234, 678, 1789};
 BinaryTreeNode bsTree = BuildTree.buildTree(inOrder, preOrder, 0);
 System.out.println(bsTree.getData());
 System.out.println(bsTree.getLeft().getData());
 System.out.println(bsTree.getLeft().getLeft().getData());
 System.out.println(bsTree.getLeft().getRight().getData());
 System.out.println(bsTree.getRight().getData());
 System.out.println(bsTree.getRight().getRight().getData());
 System.out.println(bsTree.getRight().getLeft().getData());
}

• Ray Tayek: similar: stackoverflow.com/questions/15399835/…

Answer 1

There are at least the following issues:

1. inIndex can be equal to zero, an element can be found on the first position in the inOrder list.
2. return new BinaryTreeNode(inOrder[0]); should be returned only if there are elements in the inOrder list. When the tree is not complete, you are missing leaf nodes, you should return null;
3. In rightArray you need to allocate input.length-index-1 elements, not only index.

Other then the above issues the logic is working, at least with your provided test.

• Delliardo: For suggestion 1, I tried changing the second if statement to if(inIndex >= 0), but that only causes an Array out of bounds exception to be thrown via rightArray line right[x] = input[i]; Suggestion 2, I put that return statement inside of the main if statement, and a return null where it used to be. Seems to work. Suggestion 3, I'm not sure on what you mean, or at least how to implement it. Thanks for the response!
• dan: @Delliardo 1. You need to take into account that InIndex can be zero when the buildTree function is called. 3. I was suggesting that the allocated space for the remaining right elements should be length-index-1 instead of just index, you were allocating much more. Anyway, here are all my changes to your initial submission.
• Delliardo: Oh wow, I can't believe I missed that. Thanks for the quick response. Always helps to have other people look at something!