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..

The Gateway to Computer Science Excellence

+32 votes

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

- $p$
- $p + 1$
- $n - p$
- $n - p + 1$

0

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..

0

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

try to various cases and eliminate the options.

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

0

@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.

+46 votes

Best answer

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}}$

+22 votes

0

**@**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 ???

+8

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

+7 votes

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**

0

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 ??

+1

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**

+3 votes

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**

+2 votes

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

52,223 questions

59,811 answers

201,020 comments

118,087 users