Binary Search Tree

A Binary Search Tree (BST) is a type of binary tree with a specific property: for each node, all values in the left subtree are less than the node’s value, and all values in the right subtree are greater than the node’s value. This property makes it efficient for search operations.

Key Properties of a Binary Search Tree (BST):

1. Left subtree of a node contains only nodes with keys less than the node’s key.
2. Right subtree of a node contains only nodes with keys greater than the node’s key.
3. Both the left and right subtrees must also be binary search trees.

Example:

Consider the following BST:

        8
       / \
      3   10
     / \    \
    1   6   14
       / \   /
      4   7 13

For node 8, all nodes in the left subtree (1, 3, 4, 6, 7) are less than 8, and all nodes in the right subtree (10, 13, 14) are greater than 8.

Balanced Variants of BST

Balanced variants of Binary Search Trees (BSTs) ensure that the height of the tree is kept as small as possible, typically O(log N), where N is the number of nodes.

This balance ensures efficient operations like insertion, deletion, and search.

Here are the most common balanced variants of BST:

1️⃣ AVL (Adelson-Velsky and Landis Tree)

2️⃣ Red-Black Tree