Rotate at a key

You are given the root of a binary search tree, a key that is in the tree, and a side, 'left' or 'right'. Do that rotation (lesson 2) at the node holding the key, and return the root of the whole tree.

#        6                    4
#       / \                  / \
#      4   7       ->       2   6
#     / \                      / \
#    2   5                    5   7
rotate(root, 6, 'right')     # returns the node 4

A right rotation lifts the node’s left child; a left rotation lifts its right child. The child that comes up is always there. If the node has a parent, the parent must now point to the child that came up. Move the existing nodes; do not build new ones.

The tests write a tree as a level-order list: the values level by level, left to right, with None where a child is missing. So [3, 9, 20, None, None, 15, 7] is 3 with children 9 and 20, where 20 has children 15 and 7. An empty tree is None.

Limits

• Up to 50,000 nodes; all keys are different.