edited by
6,033 views
37 votes
37 votes

A Binary Search Tree (BST) stores values in the range $37$ to $573$. Consider the following sequence of keys.

  1. $81, 537, 102, 439, 285, 376, 305$
  2. $52, 97, 121, 195, 242, 381, 472$
  3. $142, 248, 520, 386, 345, 270, 307$
  4. $550, 149, 507, 395, 463, 402, 270$

Which of the following statements is TRUE?

  1. I, II and IV are inorder sequences of three different BSTs
  2. I is a preorder sequence of some BST with $439$ as the root
  3. II is an inorder sequence of some BST where $121$ is the root and $52$ is a leaf
  4. IV is a postorder sequence of some BST with $149$ as the root
edited by

3 Answers

Best answer
39 votes
39 votes
  1. Incorrect because I & IV are not in ascending order.(Inoder sequence of BST is in increasing order)
     
  2. I is a preorder sequence of some BST with $439$ as the root . False because if $439$ is root, it should be first element in preorder.
     
  3. This is correct.
     
  4. IV is a postorder sequence of some BST with $149$ as the root, False because if $149$ is root, it should be last element in postorder
edited by
14 votes
14 votes
it should be C)

Inorder sequences are sorted. In preorder traversal root comes first and in postorder traversal root comes last.
Answer:

Related questions

32 votes
32 votes
2 answers
2
Ishrat Jahan asked Oct 29, 2014
12,444 views
How many distinct BSTs can be constructed with $3$ distinct keys?$4$$5$$6$$9$