Let $T$ be a full binary tree ${?}^1.$ Let $v$ be a node in $T,$ and define imbalance $(v)$ to be the

absolute difference between the number of leaves in the left subtree of $v$ and those in

its right subtree. If $v$ is a leaf, then imbalance $(v)=0.$

We extend the definition of imbalance to the entire tree $T$ as follows:

imbalance $(T)=ma{x}_{\text{v}\text{i}\text{n}\text{T}}$ imbalance $(v)$

$($a$)(6$ points$)$ Find an upper bound for imbalance$(T).$ Provide an example of a full

binary tree whose imbalance is maximized.

$($b$)(4$ points$)$ Draw a full binary tree $T$ such that imbalance $(T)=$ imbalance $(v)$ for

some node $v$ that is not the root of $T.$ Explicitly indicate which node is $v$ and state

imbalance $(T)$ for your tree.

$($c$)(10$ points$)$ Describe, in pseudocode, an efficient algorithm to compute imbal ance$(T).$

Provide the running time of your algorithm and justify your analysis.