brain storm - 1 year ago 68

Java Question

I am implementing code to construct

`BST(binary search tree)`

`post-order traversal array`

`binary Search Tree`

`public class BinaryTreemethods {`

public static void main(String[] args) {

int[] preOrder = { 5, 3, 1, 4, 8, 6, 9 };

int[] inOrder = { 1, 3, 4, 5, 6, 8, 9 };

int[] postOrder = {1,4,3,8,6,9,5};

static int postIndex=postOrder.length-1;

Node postordertree= buildBinarytreefromPostOrder(postOrder, 0, postOrder.length-1);

System.out.println("pre order traversal of node from postorder reconstructed tree ");

printPreOrder(postordertree);

}

private static void printPreOrder(Node tree) {

if (tree != null) {

System.out.print(" " + tree.data);

printPreOrder(tree.left);

printPreOrder(tree.right);

}

}

//this just reconstructs BT from post-order traversal elements

public static Node buildBinarytreefromPostOrder(int[] post, int start, int end){

if (postIndex<start || start > end ){

return null;

}

Node root = new Node(post[postIndex]);

postIndex--;

if (end == start){

//System.out.println("called");

return root;

}

int i = 0;

for (i=end;i>=start;i--){

if (post[i]<root.data)

break;

}

// Use the index of element found in postorder to divide postorder array

// in two parts. Left subtree and right subtree

root.right=buildBinarytreefromPostOrder(post,i+1, postIndex);

root.left=buildBinarytreefromPostOrder(post,start,i);

//root.left=buildBinarytreefromPostOrder(post,start,i);

//root.right=buildBinarytreefromPostOrder(post,i+1, postIndex);

return root;

}

}

The output when I print in

`pre-order traversal is 5 9 6 8 3 4`

Any idea where I could be going wrong?

EDIT: After swapping the order of lines for

`root.right and root.left`

the

`left tree`

`5 3 1 4 9 6 8`

Answer Source

As the root of each subtree you are taking `postIndex`

which is global for the whole structure. You should take the last element of the subarray (`end`

).

It should rather be like this

```
public static Node buildBinarytreefromPostOrder(int[] post, int start, int end)
{
if (end < start)
return null;
Node root = new Node(post[end]);
if (end == start)
return root;
int i;
for (i = end; i >= start; i--)
if (post[i] < root.data)
break;
root.left = buildBinarytreefromPostOrder(post, start, i);
root.right = buildBinarytreefromPostOrder(post, i + 1, end - 1);
return root;
}
```