Write avlInsert(node, val) that inserts val into an AVL tree and returns the root of the (sub)tree, rebalancing with rotations so that at every node the heights of the two subtrees differ by at most one.
- Nodes are
AvlNode objects with val, left, right and height (a leaf has height 1, a missing child counts as 0) - Keep every node's
height field correct, including after rotations - A duplicate value leaves the tree unchanged
- Four cases: left-left (one right rotation), right-right (one left rotation), left-right and right-left (two rotations)
- The tree's root can change when you rotate, so use the return value