Self-Balancing Binary Search Tree

Binary Search Tree

Before we begin our discussion about Self-balancing BST (or Balanced BST). Let’s recall what a BST is and why is there a need for an efficient variation.

BST is a rooted binary tree where:

• The left subtree of a node contains only nodes with smaller keys.
• The right subtree of a node contains only nodes with larger keys.

For example: