Question

Show that the number of binary search trees with \(n\) keys is given by the formula \\[\frac{1}{(n+1)}\left(\begin{array}{c}2 n \\\n\end{array}\right)\\]

Short answer

The number of binary search trees with \(n\) keys follows the \(n^{th}\) Catalan Number, which is calculated by the formula \[\frac{1}{n+1}\binom{2n}{n} \]. This was proven by establishing a link between the recursive formula for the count of binary search trees and the recursive expression for Catalan Numbers.

Step-by-step solution

Understand the Problem

The problem is to prove the formula for the number of binary search trees possible with \(n\) keys. A binary search tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child.

Find the Recursive Formula

For a BST, the number of total trees possible is the sum of the product of the number of trees possible in the left sub-tree and the right sub-tree. This can be represented with the recursive formula as: \[T(n) = \Sigma_{i=0}^{n-1} T(i) * T(n-i-1)\]

Link Recursive Form with Catalan Numbers

There is a pattern of numbers known as the Catalan Numbers. The \(n^{th}\) Catalan number is given by the formula: \[C(n) = \frac{1}{n+1} \binom{2n}{n}\] and the recursive formula for Catalan numbers is exactly the same as the formula derived in Step 2. This means that BST count is the same as Catalan numbers.

Conclusion

Then, from Step 2 and Step 3 it follows that the formula \[\frac{1}{(n+1)}\binom{2n}{n}\] is indeed the formula for calculating the number of distinct binary search trees with \(n\) keys.