Recurrence Relation for Full Binary Tree

Question

For general n, derive a recurrence relation for Bn. Here Bn denote the number of full binary trees with n vertices. I have found out that it is be B(n)=2B(n-1) +1. But after solving this equation, the final answer is O(2ⁿ). But the final answer should be

B_n = ⁿ⁻²∑_i=1 (B_iB_n−i−1)

(https://i.stack.imgur.com/0dHDu.png)

How can I derive recurrence relation for Full Binary Tree so that my final answer should be this?

Answer 1

First note that a non-empty full binary tree always has an odd number of nodes. For instance, there is no full binary tree with two nodes. So a formula that expresses only in terms of ₋₁ cannot be right. Given that ₁ is 1 (just a root node), your idea of B(n)=2B(n-1) +1 would mean that ₂ is 3, but that's not correct; ₂ is 0. Even if we would count binary trees with 2 nodes that are not full binary trees, we would never get to 3.

We can construct a recurrence relation as follows:

Given a root node, then either that root node has no children (when = 1), or it has two children, each of which root a full binary tree. Given > 1, both of these subtrees will have at least 1 node, and at most −2 nodes (to allow the right subtree to have at least 1 node): if the left subtree has nodes, then the right subtree has −1− nodes (the root is subtracted from the count). If we count all possibly shapes for the subtrees given a value for , and we count those for all the possible values of , then we come to the total number of shapes for .

This leads to the recurrence relation you quoted, but it needs to be completed with two base cases to make sense:

• ₁ = 1
• ₂ = 0
• = ⁻²∑₌₁ (₋₋₁)

Note how the recurrence expression will always be 0 when is even, because then in each term, either or −−1 is even, which by the base case of ₂ means that all involved products have a 0 factor, leading to a sum of 0.

Also, this recurrence relation is related to Catalan numbers. In fact, Wikipedia gives as example:

...It follows that is the number of full binary trees with + 1 leaves, or, equivalently, with a total of internal nodes.

So, = _(−1)/2 (when is odd)

The above Wikipedia article (see also Asymptotic approximation of Catalan Numbers) provides proof that is O(4), so is O(2)