retagged by
13,844 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

3 votes
3 votes

If total elements are n and Right Sub Tree has p elements 

then left subtree will have 

$n=root+elements in Right Subtree + Elements in  Left Subtree$

$n=1+p+Elements in  Left Subtree$

$Elements in  Left Subtree = n-p-1$

To gert $n-p-1$ elements is Left Subtree We must add root as $n-p-1+1 = n-p$

option (C)

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

0 votes
0 votes

 

The correct option is B n - p
Number 1, 2, 3,........ n are inserted into BST in some order.



Since we know total nodes = n
So, Left (root) + 1 + p = n
Left (root) = n - p - 1
Left (root) = n - (p + 1)
So, root element will be = left element + 1
= n - (p + 1) + 1
= n - p - 1 + 1
= n - p

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$