Question $4)$ A Binary Search Tree $($BST$)$ is perfectly height$-$balanced if the left and right subtrees of

any node are the same height. E$.$g$.$

The keys $1,2,3,$dots,$2^k-1$ are inserted in order into an initially empty AVL tree. Prove that the

resulting tree is perfectly balanced. $(10$ points$)$