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$?
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:
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:
Am I right ? I am afraid that I am wrong. Could you please help me out?