Binary search tree (BST) data structures are useful for searching through data by cutting the search size in half every time a value is not found.

To achieve this, we must structure the data according to some basic rules:

  • If a value is greater than the root, insert to the right of the node.
  • If a value is less than the root, insert it to the left.

In the tree to your right, the root node has a value of 5, with larger values to the right, and smaller values to the left.

This is the code for a basic binary tree, using JavaScript's psuedoclassical instantiation pattern:


      //initialize tree
      var BinaryTree = function(value, left, right) {
        this.value = value;
        this.left = left || null;
        this.right = right || null;
      };

      //insert
      BinaryTree.prototype.add = function(value) {
        if(value > this.value) {
          this.right === null ? this.right = new BinaryTree(value) : this.right.add(value);
        } else {
          this.left === null ? this.left = new BinaryTree(value) : this.left.add(value);
        }
      };
                    

In the best case scenario, a BST will yield a search time of O(lgN), where N is the number of values in the tree. However there are many instances where a BST won't achieve this best case scenario. For instance, if we always add values to our tree that are greater than the root, the tree will devolve into a list of numbers, with a lookup time of O(N)

For instance:

If we insert nodes into the BST in increasing order, the tree will devolve into a linked list. If we want to confirm that the value "6" existed, we would have to traverse every node.

This is where rotations come in handy.

Rotate Left Rotate Right

Binary search tree rotations are used to rebalance the tree structure. In the above example, rotations would be useful by reducing the number of nodes we need to traverse in order to get to the desired value

The term "rotate" can be somewhat confusing, because it's not entirely clear what action is executed when we "rotate" a tree to the left or right. The term rotate, when used in reference to a tree node, describes how the node will be placed in the data structure.

When a node is "rotated" right:

1. The node's left child becomes the new root.
2. The original node gets placed as the right child of the new root.
3. The original node's new left child becomes any nodes that were to the right of it's original left child.


      //Rotate right
      BinaryTree.prototype.rotateRight = function() {
        //check for left child
        if(this.left === null) return;
        //left tree becomes new root
        var left = this.left;
        //old root is now at the right of the new root 
        var newRight = new BinaryTree(this.value, this.left.right, this.right);

        //set correct values for the new, rotated tree.
        this.value = left.value;
        this.left = left.left
        this.right = newRight;
      };
                        
When a node is "rotated" left:

1. The node's right child becomes the new root.
2. The original node gets placed as the left child of the new root.
3. The original node's new right child becomes any nodes that were to the left of it's original right child.


      //Rotate left 
      BinaryTree.prototype.rotateLeft = function() {
        //check for right child
        if(this.right === null) return;
        //right tree becomes new root 
        var right = this.right;
        //old root is now at the left of the new root 
        var newLeft = new BinaryTree(this.value, this.left, this.right.left);

        //set correct values for the new, rotated tree
        this.value = right.value;
        this.left = newLeft;
        this.right = right.right;
      };
                        

Here are a few more trees to better help visualize the process of using binary search tree rotations. When rotating, take a close look at how the root node is moving. Visit Wikipedia's page on tree rotations for more information.