I had two specific type of questions involving Binary Search Tree (not simple Binary Tree) traversals :
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.)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,
- for all x-order traversal outputs, we can state whether it is valid or not.
- 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.