3
$\begingroup$

I'm trying to find a recurrence relation for how many full binary trees there are with n nodes. However, once I get to n = 11, it's there's a lot of trees to keep track of. I've written out the cases for $$n \in [1,9] $$ where n is odd but I can't figure out the pattern.

At n=1, I have 1.

n = 3, I have 1

n = 5 : 2 /// n = 7 : 5 /// n = 9 : 14

Basically I took the leaves from the previous nth tree I created and added 2 nodes to each leaf for all possible full binary trees then got rid of duplicates. I.e for n = 7, I took leaves from n = 5, which is 3 and added 2 nodes to each leaf from all the fbts possible when n = 5 (which is 2) and so I end up with 6 fbts, but there's 1 duplicate so I subtract 1 to end up with 5 distinct fbts.

Any help on figuring out the pattern or atleast how many distinct fbts with n nodes?

$\endgroup$
  • $\begingroup$ You need to define "distinct" carefully. This link may be of interest: durangobill.com/BinTrees.html $\endgroup$ – Alexis Olson Nov 1 '16 at 18:38
  • $\begingroup$ There is a very interesting video about Catalan numbers and how it is related to binary trees and many other things: youtube.com/watch?v=etzcN6g-vNY It is in French sorry, but if you select French subtitles + auto translation it gives fairly good English. (you can skip directly to 6:00) $\endgroup$ – zwim Dec 23 '18 at 2:27
  • $\begingroup$ Relevant post from CS-SE. $\endgroup$ – JavaMan Dec 23 '18 at 3:49
2
$\begingroup$

See: Catalan Numbers

You can use the number $C_n$ to describe the number of binary trees with $n+1$ leaf nodes, that is, $2n + 1$ nodes total.

EDIT: Here's the full reasoning.

We have $C_0 = 1$, and suppose we have $C_0, \ldots, C_n$, the number of full binary trees with up to $n + 1$ leaf nodes, and we want $C_{n+1}$. Given a root node, we just need $k$ leaf nodes on one side, and $n + 1 - k$ leaf nodes on the other, for all values of $k$ from $1$ to $n$. Since there's $C_k$ ways of choosing trees for one side, and $C_{n+1-k}$ on the other, there's a total of $C_k \cdot C_{n -k}$ trees for a given $k$.

Solve for this recurrence:

$$ C_0 = 1, \qquad C_{n+1} = \sum_{k=0}^{n}C_kC_{n-k}$$

The solution is the Catalan Numbers $C_n = \frac{(2n)!}{(n+1)!n!}$.

$\endgroup$
  • $\begingroup$ Are you not double counting some cases? $\endgroup$ – gen Oct 11 '17 at 13:03
  • $\begingroup$ Maybe it's worth adding a note about this to your answer? $\endgroup$ – gen Oct 11 '17 at 19:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.