The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+30 votes
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 by Boss (16.3k points)
retagged by | 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.

5 Answers

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

by Boss (21.3k points)
edited by
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)
+20 votes
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
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

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

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

+2 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

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

@VIDYADHAR SHELKE 1

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

Thanks !

+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

by Boss (11.2k points)
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,309 questions
55,743 answers
192,226 comments
90,495 users