6

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?

Chubbles
  • 359
  • You need to define "distinct" carefully. This link may be of interest: http://www.durangobill.com/BinTrees.html – Alexis Olson Nov 01 '16 at 18:38
  • There is a very interesting video about Catalan numbers and how it is related to binary trees and many other things: https://www.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) – zwim Dec 23 '18 at 02:27
  • Relevant post from CS-SE. – JavaMan Dec 23 '18 at 03:49

1 Answers1

5

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!}$.

Larry B.
  • 3,384