GATE IT 2008 | Question: 72

Question

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?

• A. I, II and IV are inorder sequences of three different BSTs
• B. I is a preorder sequence of some BST with $439$ as the root
• C. II is an inorder sequence of some BST where $121$ is the root and $52$ is a leaf
• D. IV is a postorder sequence of some BST with $149$ as the root

Comments

I have one doubt.

As option C is not true in all cases .

Then if one of the option is NONE of these ..Then which one should be marked?

---

option C says “inorder sequence of some BST”

Answer 1

• A. Incorrect because I & IV are not in ascending order.(Inoder sequence of BST is in increasing order)
   
• B. 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.
   
• C. This is correct.
   
• D. 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

Comments

@Mahima, you are true but in the question all the other options are incorrect and also the question says which of the following is true not "always true"

---

@Mahima

II is an inorder sequence of some BST where 121 is the root and 52 is a leaf

some BST means there exists a BST with these properties.

---

those who are saying option C is not correct in all the cases…. 

II is an inorder sequence of some BST where 121 is the root and 52 is a leaf.

 

Answer 2

it should be C)

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

Comments

 pls justfy........."where 121 is the root and 52 is a leaf"

---

apply AVL rotation and do balance it you will got 52 at the end

Answer 3

Answer should be option C

Comments

from where 142 and 52 coming explain?