a$)$ Define a height balanced binary search tree.

b$)$ Show that the binary search tree constructed with nodes as $8,6,10,4,7,9,11,$

$3,5,2$ is not height$-$balanced. You should first show the step$-$by$-$step

construction of the tree taking the first data as the root.

c$)$ Apply appropriate AVL rotation on the tree in $($b$).$ Verify that the rotation

indeed achieves the desired result.

d$)$ Prove or disprove: A complete graph is always connected.

a$)$ Define $-$notation with proper explanation.

b$)$ Using the definition in $($a$),$ prove that $n^2-\frac{3n}{2}=(n^2).$

c$)$ Find the solution to the recurrence relation $T(n)=2T(\sqrt[\phantom{2}]{n})+1$ using the

substitution method.