retagged by
13,249 views
53 votes
53 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

  1. $p$
  2. $p + 1$
  3. $n - p$
  4. $n - p + 1$
retagged by

7 Answers

Best answer
70 votes
70 votes

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

edited by
28 votes
28 votes
from 1,...n elements p elements are on the right. so root or first inserted will be at n-p
11 votes
11 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

6 votes
6 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

Answer:

Related questions

27 votes
27 votes
4 answers
1
64 votes
64 votes
7 answers
3
Ishrat Jahan asked Nov 3, 2014
22,451 views
In a binary tree, for every node the difference between the number of nodes in the left and right subtrees is at most $2$. If the height of the tree is $h 0$, then the m...
67 votes
67 votes
2 answers
4