2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$

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.