2.9k views

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

1. $p$
2. $p + 1$
3. $n - p$
4. $n - p + 1$
in DS
retagged | 2.9k views
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
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.

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

by Boss (21.3k points)
edited
0
ok so ( n-(p+1) +1 )th element at root.
+1

Root is 1 element.

RST takes p nodes then LST= n-p-1 nodes

I think it must be 1,2,3,......,n-p-1,n-p,n-p+1,.....n

So root is n-p

0
you are correct just take - (minus) comman  n-p-1   =>  n-(p+1)
from 1,...n elements p elements are on the right. so root or first inserted will be at n-p
by Boss (11k points)
0

@Arjun SIR

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

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

by Loyal (7.1k points)
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 ??

0
@pooja

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

so x must be n-p.
+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

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

by Junior (759 points)
0
those who still doubt remember BST is always in sorted order...your root node always comes before right subtree
+1

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

Thanks !

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

by Boss (11.2k points)

1
2