construct binary search tree from Post-order traversal in Java

Question

I am implementing code to construct BST(binary search tree) from a given post-order traversal array following this algorithm. I do not get back the binary Search Tree back. I am getting something that makes no-sense. here is my code

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 which is not correct.

Any idea where I could be going wrong?

EDIT: After swapping the order of lines for root.right and root.left (commented out one were before), the left tree is build correctly, but the right tree is not. The output I get is 5 3 1 4 9 6 8

Answer 1

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