Given the postorder sequence 1, 2, 3, 0, 7, 9, 8, 6, 5, 4 of the keys of nodes in a binary search tree, find that tree.

Question

Given the postorder sequence 1, 2, 3, 0, 7, 9, 8, 6, 5, 4 of the keys of nodes in a binary search tree, find that tree.

I think i've done this right but i'm not sure.

Answer 1

While the postorder traversal is correct, it is not a BST. For example, $9$ is to the left of $4$. The idea here is to take the last number as the root, partition the keys less than the root into the left subtree and the keys greater than the root into the right subtree, and recurse. So you should get:

Answer 2

Hint: In-order traversal of Binary Search Tree is always sorted order.

Now, follow this procedure: Algorithm for constructing BST from post-order traversal.