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?


I think your answer is correct. Without bothering with recursive relations, we can observe that the only semi-balanced binary trees are perfect trees.

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.

Nitpicky thing: you should take the upper integer part of the lower limit of the sum, and the lower integer part of the upper limit.

  • $\begingroup$ It makes sense, so if I am not wrong the inequality reduces to L(m)=R(m) and T(N) = 1 when N = odd, T(N) = 0 when N = even? $\endgroup$ – avocado Mar 25 '18 at 7:32
  • $\begingroup$ Rather, $T(n) = 1$ if $n = 2^k-1$ for some $k$, $0$ otherwise. $\endgroup$ – quicksort Mar 25 '18 at 7:37
  • $\begingroup$ Yeah. That seems right $\endgroup$ – avocado Mar 25 '18 at 7:42

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.