Question
Consider a binary tree; define its height as $0$ if it consists of a single node, and $1$ plus the maximum height of its subtrees otherwise. For a generic node $u$ in the tree, let $P(u)$ and $Q(u)$ be, respectively, the number of nodes in the subtree rooted at the left and at the right child $u$ (if such a child exists, or $0$ otherwise).
Considering only trees such that $|P(u)-Q(u)|\leq 2$ for every node $u$, what is the minimum number of nodes $T(h)$ in any such tree of height $h$?
My Approach
I was thinking that if the above question would have been the same but with the condition $|P – Q| \leq 1$, then it would be equivalent to finding the minimum number of nodes $(T(h))$ in an AVL tree of height $h$, which is:
$T(h)=T(h-1)+T(h-2)+1$
$T(0)=1$
$T(1)=2$
This recursive equation is derived from the fact that # of nodes in Left subtree(LS) should not be equal to Right subtree(RS) because then the nodes will not be minimal. To make it minimal, we need to have $LS \gt RS$ or $RS \gt LS$ i.e put as many less nodes in LS than RS (or vice versa) without violating $|P – Q| \leq 1$.
Keeping this things in mind if we try to solve for the constraint
$|P – Q| \leq 2$
the recursive equation should become:
$T(h)=T(h-1)+T(h-2)+2$.
Am I right ? I am afraid that I am wrong. Could you please help me out?
The idea of using a recurrence is a good one, even though the specific recurrence you guessed is not correct. Denote by $T(h)$ the minimum number of nodes in a binary tree of height $h$ under your constraints (let's call it an "almost balanced" tree).
The first thing to observe, is that, for any $h$, you can always build an almost balanced tree of height at most $h$ with any number $n$ of nodes between $2^{h+1}-1$ (a complete binary tree of height $h$) and $0$ (the "empty" tree). This is easily proved by induction. Then:
$T(h)=1+T(h-1)+\max(0,T(h-1)-2)$
The first term on the right-hand side, $1$ is the root. The second term $T(h-1)$ is the minimum number of nodes in the "tallest" subtree, which must have height $h-1$). The third term is the minimum number of nodes in the other, possibly empty, subtree - which can be no smaller than $0$ (obviously) and also no smaller than $T(h-1)-2$ if you want the main tree to be almost balanced.
The basis of the recurrence is easy, $T(0)=1$. Solving the recurrence is a little harder because of the nasty $\max$; fortunately, it should be an active constraint only for very small trees, so we can just solve the recurrence case by case until we get to a $T(h)\geq 2$, and then leave out the max. In fact,
$T(1)=1+T(0)+\max(0,T(h-1)-2)=1+1+0=2$
so already for $h\geq 2$, we can leave out the max, and obtain a simpler: $T(h)=1+T(h-1)+(T(h-1)-2)=2T(h-1)-1$.
The last recurrence can be easily solved to obtain:
$T(0)=1$, $T(1)=2$, $T(h)=2^{h-1}+1$ for $h\geq 2$.