World's most popular travel blog for travel bloggers.

[Solved]: Binary Search Tree Traversal output validity and unique BST construction

, , No Comments
Problem Detail: 

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.

Asked By : Mahesha999

Answered By : Hendrik Jan

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.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback