retagged by
13,848 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
71 votes
71 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

9.6k
views
4 answers
28 votes
Ishrat Jahan asked Nov 3, 2014
9,582 views
A binary search tree contains the numbers $1, 2, 3, 4, 5, 6, 7, 8.$ ... , 1, 4, 3, 6, 7, 8, 5$2, 1, 4, 3, 7, 8, 6, 5$
8.2k
views
2 answers
24 votes
Ishrat Jahan asked Nov 3, 2014
8,196 views
The following C function takes a singly-linked list of integers as a parameter and rearranges the elements of the list. The list is represented as pointer to a structure. The function is called with ... , 2, 5, 4, 7, 6$2, 3, 4, 5, 6, 7, 1$
23.3k
views
7 answers
64 votes
Ishrat Jahan asked Nov 3, 2014
23,262 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 minimum number ... $2^{h-1} + 1$2^h - 1$2^h$
18.2k
views
2 answers
69 votes
Ishrat Jahan asked Nov 3, 2014
18,172 views
A function $f$ defined on stacks of integers satisfies the following properties. $f(∅) = 0$ and $f (push (S, i)) = max (f(S), 0) + i$ for all stacks $S$ and integers $i$. ... , 2, -1, 2$ in order from bottom to top, what is $f(S)$?$6$4$3$2$