Remember to turn in a neat final draft of this homework on a separate sheet of paper.

1 Rotations

1. Draw the tree that would result after performing a left rotation at node 13 of the following tree:
   
2. Copy the following tree and write in the heights at every node. Then perform any rotation(s) to make it an AVL tree and show the result.
   

2 AVL insertions

For the next two problems, start with an empty AVL tree and insert each of the given nodes, in the order given. Rebalance the AVL tree after every insertion. You do not need to draw every single step separately, but you must draw the tree immediately before every rotation, and say what the rotations are.

3. 29, 9, 12, 89, 17, 84
4. 77, 82, 2, 25, 54, 27, 21, 95, 65

3 AVL height

For any integer \(h\), the smallest BST of height \(h\) has exactly \(h+1\) nodes; this would be a "degenerate tree" like we've discussed many times in class.

But of course that's not possible for an AVL tree, since it would be unbalanced. The question is, how few nodes could an AVL tree of height \(h\) have?

5. For each \(h = 0, 1, 2, 3, 4\), draw an AVL tree that has height \(h\) and has as few nodes as possible. For example, the smallest AVL tree with height \(h=2\) has 4 nodes. Draw each tree up to \(h=4\) and also write down the number of nodes in each one. Do this in a neat and clear way so it's easy to see each tree and its size.
6. BONUS: Tell me the least number of nodes in an AVL tree of height 20. You do not have to draw the tree!