Answer the following question

Question

In 28 my answer is c but answer given is d.

Q. 28 The number 1,2 , $\qquad$ $n$ are inserted in binary tacarch tree in some order in the resulting tee the right subtree of the root contains p nodes The first number to be inserted in the tree must be

• A. 19
  
• B. $p+1$
  
• C. $0=p$
  
• D. $n=0+1$

Comments

Total there are n elements out of which p elements are present in the right subtree. Now remaining element would be n-p out of which one element would be root So the left subtree will contain n-p-1 elements.

Since it is a binary search tree, so left subtree will have all the values less than root and similarly in the right subtree all the values will be greater than root.

1,2,..............n-p-1, n-p, n-p+1,.........................n

So the first number to be inserted in the tree must be n-p

 

Answer 1

The first inserted element must become the root and as per question we have $p$ elements on right subtree which means $p$ elements are larger than the root. So, out of $n$ elements, the root must be $n - p$.