Problem $4.$ "Balanced" Binary Trees $(10$ points$)$

Consider a binary tree $T,$ with $|T|=n$ nodes. For a given node $x$ in $T,$ we can say that the subtree

rooted at $x$ is "approximately balanced", $AB(x),$ if $|x.$right $|2*|x.$left $|$ and $|x.$left $|2*|x.$right $|.$

$($a$)$ What is the maximum height of a binary tree $T$ with $n$ nodes if $AB(x)$ holds? $($Recall that the

height of a one$-$node tree is $0.)$

Solution:

$($b$)$ Prove that, if $AB(x)$ holds for every node $x$ in a tree $T,$ then the number of nodes in $T,$

$|T|\frac{3}{2}$ height $(T).$ Use induction on on the height of $T$ for your proof, with the base case being a

tree of height $0.$

Solution: