Proof that a unique BST can be reconstructed from a preorder (or a postorder) traversal unambiguously

Question

For a Binary SEARCH Tree, a preorder or a postorder traversal is sufficient to reconstruct its original binary search tree unambigiously.

But I cannot find a proof or a explanation for why it is so.

For inorder traversal, it is trivial to come up with a counter-example to show that there may be many different BSTs correspond to a given inorder traversal.

Is there any proof or reference that a preorder or a postorder traversal is sufficient to reconstruct its original BST unambiguously?

This is for a BST, not for a general binary tree.

Answer 1

By the definition of pre-order traversal, it is guaranteed that root will be the first element.

Now, given the root, there is a unique set of elements that will come in the left half of the root - i.e. all elements having value less that root->val.

Likewise for the right subtree.

Now, we have to apply the above logic recursively for the left subtree and the right subtree.

Since, post-order traversal is just the reverse of pre-order traversal on the reverse tree, the same logic applies to post-order traversal too.