# Doubt regarding binary trees and counting

Question:

A binary Tree T is semi-balanced, if for every node m in T: $$\frac{R(m)}{2} <= L(m) <= 2*R(m)$$ where, L(m) is the number of nodes in the left sub-tree of m and

R(m) is the number of nodes in the right sub-tree of m.

Write a recurrence relation to count the number of semi-balanced binary trees with N nodes.

My Attempt:

Let T(N) denote the number of semi-balanced trees with N nodes.

For N = 1, T(N) = 1 (Trivial)

For N > 1, T(N) can be found by splitting N into 3 parts, a root, a left subtree and a right subtree, let M be the number of nodes in the left portion, then the N - M - 1 is the number of nodes in the right portion, so by the constraint in the question,

$$\frac{N-1}{3} <= M <= \frac{2*(N-1)}{3}$$

So for N > 1,$$T(N) = \sum_{M=\frac{N-1}{3}}^{\frac{2*(N-1)}{3}} T(M) * T(N-M-1)$$

However, the answer is given as,$$T(N) = \sum_{M=\frac{N-1}{3}}^{\frac{2*(N-1)}{3}} 2 * T(M) * T(N-M-1)$$

Why is there a factor of 2 in the solution?

In fact, the only semi-balanced binary trees of heights $1$ and $2$ respectively are perfect (obvious for height $1$, casework for height $2$). Now, assume by inductive hypothesis that all semi-balanced binary trees of height at most $n$ are perfect trees. By definition, the root of a semi-balanced binary tree of height $n+1$ must have two semi-balanced subtrees as children, one of which has height $n$. By inductive hypothesis, that subtree is exactly the perfect binary tree of height $n$. By inductive hypothesis and definition of semi-balanced binary tree, the other subtree must therefore be too the perfect binary tree of height $n$, which completes the proof.
We can see that for e.g. $N=7$ the presence of a factor $2$ yields a wrong answer.
• Rather, $T(n) = 1$ if $n = 2^k-1$ for some $k$, $0$ otherwise. – quicksort Mar 25 '18 at 7:37