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

The first number to be inserted in the tree must be

What does it exactly means ?

According to the answers given above u r giving the count of nodes in the left subtree...it is the count,ri8?

It doesn't mean first number..

---

Go with options always good in an exam.

try to various cases and eliminate the options.

But in case you understand logic behind it and concept go with Standard resources

---

@Nitesh Methani Root is always the first element to be inserted, to find root node we are counting the total nodes present in its LST and RST.

---

Try a simple example n=6,p=2

1,2,3,4,5,6 are inserted 

Right subtree will have 2 numbers (5 and 6)

So Now first number inserted should be 4 

and 4 =  6-2 = n-p option C 

---

Thanks Mitali mam, it helped me visualise 😌

---

nice mam.

---

n-p

---

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

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

Answer 4

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