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

https://youtu.be/E-YzK7_-u_0?t=10430 hope this timestamp helps you.

---

• Total n elemnts
• p elements are in the right subtree
• 1 element is the root

So

Left Subtree=n−(p+1) 

• every element in the left subtree is smaller
• every element in the right subtree is greater

Suppose the elements are

1,2,3,…,n 

Since there are

n−(p+1) 

elements smaller than the root, the root must be the next larger element.

So root's rank is

(n−(p+1))+1 

Simplify:
Answer = n-p

exa. 

Suppose there are 10 elements.

The right subtree has 3 elements.

So:

• Right subtree = 3 elements
• Root = 1 element
• Left subtree = 10−(3+1)=6 elements
•  
• Those 6 elements are
  1,  2,  3,  4,  5,  6 
  The root is the next element after these 6 elements.
•  
• 
  1  2  3  4  5  6 | 7 | 8  9  10
  <-- Left -----> Root<--- Right
•  

  Since 6 elements come before the root, the root is the

  6+1=7th 

  smallest element.

  That is why we add 1.

---

suppose n=8 and p=3,
1,2,3,4,5,6,7,8

clearly left subtree elements: 6,7,8

root node: 5 first element to be inserted in the tree

right subtree elements must be:1,2,3,4

only option c correct as n-p=8-3=5
 

Answer 1

Option is C.

P: # elements in RST

$\Rightarrow$ Depending on $X,$ some number will go LST $\notin$ RST

$\Rightarrow$ 

Remaining elements for LST:  $n- (p+1)$

$\underbrace{1,2,\ldots,n-(p+1)}_{\text{LST}\\n-(p+1)\\ \text{elements}}\qquad \underbrace{n-p}_{\text{Root}\\1\\ \text{element}}\qquad \underbrace{(n-p)+1,\ldots,n}_{\text{RST}\\p\\ \text{elements}}$

Comments

if it is given that numbers are inserted in any order,then why we are using only ascending order to get the answer.

---

Your solution is valid only when the elements are inserted in ascending order, buddy. 

But in the question, it is mentioned that the elements are inserted in any order. 

So, we can’t be sure that n-p will be the root here. 

For example – if p=5 and n= 12, then we can say that the 7^th element will be the root, but that element can have any value, depending upon the values of the immediate predecessor and successor.

 

---

@svmk_18 whatever be the order buddy, inorder is always sorted. And the example given by you if p=5 and n=12 then 6 nodes will be in the LST having order as 1,2,3,4,5,6. and in the RST 8,9,10,11,12. Then 7 will be the root. Whatever be the order LST and RST are same.

Answer 2

from 1,...n elements p elements are on the right. so root or first inserted will be at n-p

Comments

@Arjun SIR
PLease Explain Question 

What is  p here ? 
Is p denotes number of nodes  in right subtree ?
Suppose Root is x then p number of nodes on the right subtree then what is x ?

If this is the case then how x  is n-p ??
Suppose my right subtree contain 3 elements 10 15 and 20 , Here p is 3 . Does this mean Root is n-3 ???

---

Please understand the question carefully, The given binary search tree contain n elements, and the elements are 1, 2,..., n. Suppose in your example since 20 is biggest number , assume 1, 2,...20 are there. but the given possibility of only 10, 15, 20 only on right subtree is not possible. if it was possible 11,12,13,14,16,17,18,17 should be on left subtree or root. for a BST it is not possible. so if p=3, only the last three elements 18,19,20 can be on the right sub tree. 17 will be root and 1,...16 will be on the left sub tree. The comment given below by Mr. pC in pictorial form well explain the concept

---

• In total there are n elements. p of those are in right sub tree.
• Now we there are n-p elements.
• Of that n-p-1 elements will be in left subtree (-1 as have to keep one element for root)
• So the next element will be (n-p-1) + 1 => n-p

Answer 3

If the right subtree of the root contains p nodes then the first number to be inserted in the tree must be n-p

and If the left subtree of the root contains p nodes then the first number to be inserted in the tree must be p+1

Comments

Sorry i dont get it ... can i say If the right subtree of the root contains p nodes then the first number to be inserted in the tree must be p+1 ??

---

@pooja

total elements (n) = x( root) +p(right subtree) + n-(p+1)( left subtree)

so x must be n-p.

---

Puja Mishra 

nupss...u can't say that...take an example and try to figure out that...

eg. 1,2,3....10 here n=10

suppose root is 5

now do urself and draw a tree by taking 5 as a root...u will find that there are 5 elements in right subtree, so p=5....and root becomes n-p = 10-5=5 which we takes initially.

so, If the right subtree of the root contains p nodes then the first number to be inserted in the tree must be n-p

---

Yes, if you cannot understand in terms of variables, try taking some small examples and applying the options on it. it helps most of the time.

Answer 4

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 5

Let the numbers 1,2,3,4,5 are inserted in a binary search tree in ascending order.

The resulting tree, look like this:-

the right subtree of the root contains 4 nodes. The first number to be inserted in the tree must be
from option 
Answer will be C. 5-4 = 1

Comments

those who still doubt remember BST is always in sorted order...your root node always comes before right subtree

---

@VIDYADHAR SHELKE 1

Actually that's the key point i m in the search for.

Thanks !

---

Nice, I thought only I knew about this, AVL tree visualisation software. Hehehe

Answer 6

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