How to prove the number of unlabeled binary trees is the same as the number of BSTs possible

Question

How to prove that the number of unlabeled binary trees is the same as the number of Binary Search Tree possible. I know the number of binary search tree is equal to nth catalan number but how would I prove that this is equal to the number of unlabeled binary tree.

Answer 1

HINT: There are a couple of reasonable approaches.

• You could show that if $T$ is a binary tree with $n$ nodes, there is only one way to label the nodes $1,\ldots,n$ that makes $T$ a binary search tree. This isn’t too hard. Start at the root. If there are $\ell$ nodes in its left subtree, the only possible number to assign to it is $\ell+1$; why?

• You could show directly that there are $C_n$ binary trees on $n$ nodes. This is most easily done by induction on the number of nodes, using the fact that $C_{n+1}=\sum_{k=0}^nC_kC_{n-k}$, with $C_0=1$.