#gatebook_dsa

Question

The number of binary search trees with 2n+1 keys where median is the root?

• A. $(\frac{2nc_n}{n+1})^2$
• B. $(n!)^2$
• C. $(2n+1)!$
• D. it depends on the values of the keys

Answer 1

Since 2n+1 key sare given .

Median is middile element of sorted sequence.

so if if root is median then left of subtree n nodes are there and right also n nodes are there of median element.

so for left side  with n element how many BST are possible = $\frac{\binom{2n}{n}}{n+1}$

so for right side  with n element how many BST are possible = $\frac{\binom{2n}{n}}{n+1}$

total BST are = $\frac{\binom{2n}{n}}{n+1} \times \frac{\binom{2n}{n}}{n+1} = \left (\frac{\binom{2n}{n}}{n+1} \right )^2$

Comments

What if all the $2n+1$ keys are same?

---

@air1 only 1 possibility.

Take one example & try u ll get it.

---

So is the answer dependent on the value of keys?