brain storm brain storm - 3 months ago 20
Java Question

construct binary search tree from Post-order traversal in Java

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

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