Binary search tree. Counting.

Question

How many BSTrees can be constructed from given set: $\{1,2,3,4,5\}$? I have no idea how to solve it. Please help me. Thanks in advance.

Answer 1

The number of binary search trees over $n$ distinct elements is given by the $n$-th Catalan number $C_n = \prod_{k=2}^n \frac{n+k}{k}$. The answer to your question is thus 42, as always :)

Think about the possible paths from the lower left corner to the upper right corner in an $n\times n$-grid, if only moves pointing rightwards or upwards are allowed and no path is allowed to cross the diagonal. Each of these paths can be mapped to a distinct binary search tree.

The formula for $C_n$ can be proven by induction and calculated by dynamic programming.

Answer 2

There are several ways to visualize and derive the Catalan numbers $C_n$ in addition to the path through a square grid, mentioned above. One is to count all the ways in which $n+1$ elements can be grouped by parentheses (i.e., where there are $n$ boundaries): So for $n=3$, the number of distinct ways to put parentheses around 4 elements is 5: $((ab)c)d$, $(a(bc))d$, $(ab)(cd)$, $a((bc)d)$, and $a(b(cd))$. Thus $C_3 = 5$. A method more closely related to your direct question is: How many ways can you construct a binary tree with $n$ (non-terminal) vertexes such that there is ), 0, 1 or 2 descendants from each vertex, distinguishable by being on the "left" or the "right." Try sketching all three-vertex trees under these conditions to confirm that $C_3=5$. Once you have all such trees for a given $n$, you can derive the Catalan number $C_{n+1}$ by induction.