Binary Search Tree Traversal output validity and unique BST construction

Question

I had two specific type of questions involving Binary Search Tree (not simple Binary Tree) traversals :

1. Given x-order traversal output of BST, can we state if it is valid or invalid output?

   (For example, this: [3,2,1,4,6,7,8,5] can be valid postorder traversal output, but this: [4,1,3,2,6,7,8,5] cannot be.)

2. Given x-order traversal output of BST, can we draw unique BST?

Put Pre, Post, In and Level in x. So there are actually 8 questions.

I didnt find any place discussing these all. But after a bit of thinking I realized that,

1. for all x-order traversal outputs, we can state whether it is valid or not.
2. for all x-order traversal outputs except the inorder, we can draw unique BST.

This is really confusing me. Especially in case of inorder. Logically, it seems that if we can construct unique BST for given x-order traversal output, then we can say that for that x-order traversal output, we should be able to tell whether the output is valid or not. But this does not seems to be correct, since in case of inorder traversal, we can tell if the given output is valid or not but we cannot construct the corresponding unique BST.

Answer 1

I believe you are correct. The hard part is convincing yourself why this is true, I guess.

The key to the riddle is the root. preorder, postorder and levelorder all have the root at first or last position. Once the root is known all elements smaller go in the left subtree and those larger go right. Thus reconstructing the tree from its order is a recursive process.

Inorder always yields the elements from small to large, so there the situation is completely different. There is no unique tree, and any tree that is built by adding the elements as a BST will do.