Exercise $2.$

Calculating the tree imbalance

$.$

$[20$ points$]$

Let

$$

be a

full

binary tree

$1$

$.$ Let

$$

be a node in

$$

$,$ and define

imbalance

$($

$$

$)$

to be the

absolute difference between the number of leaves in the left subtree of

$$

and those in

its right subtree. If

$$

is a leaf, then

imbalance

$($

$$

$)$

$=$

$0$

$.$

We extend the definition of

imbalance

to the entire tree

$$

as follows:

imbalance

$($

$$

$)$

$=$

max

$$

in

$$

imbalance

$($

$$

$)$

$.$

$($a$)(6$ points$)$ Find an upper bound for

imbalance

$($

$$

$)$

$.$ Provide an example of a full

binary tree whose imbalance is maximized.

$($b$)(4$ points$)$ Draw a full binary tree

$$

such that

imbalance

$($

$$

$)$

$=$

imbalance

$($

$$

$)$

for

some node

$$

that is

not

the root of

$$

$.$ Explicitly indicate which node is

$$

and state

imbalance

$($

$$

$)$

for your tree.

$($c$)(10$ points$)$ Describe, in pseudocode, an efficient algorithm to compute

imbalance

$($

$$

$)$

$.$

Provide the running time of your algorithm and justify your analysi