  Close Menu Navigation

Counting Binary Trees (The Hard Way)

In this post, we prove the closed form of a nonlinear recurrence corresponding to the count of binary trees with nodes.

Suppose I have a binary tree of internal nodes, we can count all possible such configurations by looking at the tree like where each internal subtree with nodes is a vertex plus two trees whose node-sum is , or This is pretty fucking hard to solve. Here’s a way where we do not need to appeal to generating functions.

Let’s begin with a reasonable hypothesis: is a first order recurrence. After groping around for a while, we find that this is actually a nonlinear homogeneous recurrence: Here’s the first couple of terms: No obvious pattern yet, but if we look at the sequence , we see that it looks like Notice how the primes in the denominator are exactly the right amount of spacing apart ( is 2 away from , 4 away from , etc). Furthermore, for the nonprime denominators, they are always a divisor of what the expected value there is supposed to be (for example, the in the number right before the ), this seems to suggest that there’s always an inverse affine factor between two elements of the sequence. Since the denominator of is , let’s conjecture that In fact, the sequence looks really nice! why, this is just the sequence , so we can pretty accurately guess that Warning: This is a really tedious proof; the point is to construct a series that cancels out the on the denominator of at each step of the induction.

Proof: By strong induction, for some , suppose that we have already shown that .
Consider the series In the case, this looks like notice that we can flip the order of this series and add with itself to get By appealing to the induction hypothesis on , we also have So, above, we’ve derived the following: Substituting the left into the right, we get which concludes the proof. This recurrence allows us to write Notice that this is the same as Phew.

Posted By Lee

Woosh

• Anderson Torres

What if you have put some interesting restriction on the binary tree? Example: what about AVL trees?