number of complete binary trees with n+1 leaves is catalan

Statement

In our case, we mean exactly binary trees (for 212, I will omit a definition) where each node either has 0 or 2 children. In other words, every node either has a left and right child or is a leaf.

Then, the number of binary trees with $n + 1$ leaves is equal to $C_{n}$ , the Catalan numbers.

Proof

We shall construct a bijection between binary trees and valid parenthesizations. Roughly,

each leaf corresponds to a letter
if two leaves are children of the same vertex, then put a parenthesis together
iterate upwards