GATE IT 2005 | Question: 12

Question

The numbers $1, 2, .\dots n$ are inserted in a binary search tree in some order. In the resulting tree, the right subtree of the root contains $p$ nodes. The first number to be inserted in the tree must be

• A. $p$
• B. $p + 1$
• C. $n - p$
• D. $n - p + 1$

Comments

nice mam.

---

n-p

---

Thanks for explanation it hepls me a lot to grap the concept

Answer 1

If total elements are n and Right Sub Tree has p elements 

then left subtree will have 

$n=root+elements in Right Subtree + Elements in  Left Subtree$

$n=1+p+Elements in  Left Subtree$

$Elements in  Left Subtree = n-p-1$

To gert $n-p-1$ elements is Left Subtree We must add root as $n-p-1+1 = n-p$

option (C)

Comments

can you explain the last line.

 

“To get n−p−1 elements is Left Subtree We must add root as n−p−1+1=n−p”

 

Answer 2

We can solve this question by assuming some values like 

Suppose we have 1,2,3,4 nodes it means n =4 

1- If right subtree have 0 elements so p=0 put this value in option C which is n-p = 4-0 = 4 

so we have to insert 1st element is 4 in this case BST is left skew

2- If right subtree have 1 element so p=1 put value in option C so n-p= 3 

so 1st element is 3 in this case 4 is in right remaining in left 

3- If right subtree have 2 element so p=2 put value in option C so n-p= 2 

so 1st element is 2 in this case 3 and 4 will be in right remaining 1 in left

4- If right subtree have 3 element so p=3 put value in option C so n-p= 1 

so 1st element is 1 in this case 2,3,4 is in right it is right skew tree  

we can verify by this way in remaining options too but the correct option is C

Answer 3

 

The correct option is B n - p
Number 1, 2, 3,........ n are inserted into BST in some order.


Since we know total nodes = n
So, Left (root) + 1 + p = n
Left (root) = n - p - 1
Left (root) = n - (p + 1)
So, root element will be = left element + 1
= n - (p + 1) + 1
= n - p - 1 + 1
= n - p