Binary Search Tree Rotation

Why do you rotate a Binary Search Tree?

Binary Search Tree roatation is important in rebalancing trees and for reorganization.

This can be especially helpful in other type of trees, such as the Red Black Tree.

How do you rotate a Binary Search Tree?

Steps for a right rotation

  1. Set the root's left to the left child's right child
  2. Set the parent of that grandchild to the root
  3. Set the left child's right child to be the root
  4. You have successfully rotated a tree to the right!
Image of nodes being rotated right

Steps for a left rotation

  1. Set the root's right to the right child's left child
  2. Set the parent of that grandchild to the root
  3. Set the right child's left child to be the root
  4. You have successfully rotated a tree to the left!

For more information, you read up on it here!