A right rotation at node y lifts its left child x into y's place:
y x
/ \ / \
x C ==> A y
/ \ / \
A B B C
A, B and C keep their contents and their order, so an in-order walk reads the same values before and after; only the shape changes.
Write rotate_right(root) returning the new root of the rotated subtree. If root is None or has no left child, return root unchanged.
Examples
Input: root = build_tree([3, 2, None, 1])
Output: tree_to_list(...) == [2, 1, 3]
Input: root = build_tree([1, None, 2])
Output: tree_to_list(...) == [1, None, 2]
Explanation: nothing to pivot, because there is no left child.
Constraints
0 <= number of nodes <= 10**4- The rotation changes at most two links; do not rebuild the subtree.
Goals
- Perform the single rotation that every balanced tree is built on
- Re-hang exactly one subtree and leave the in-order sequence unchanged
- Leave a tree with no left child alone