List the types of Binary Search Tree. Explain Insertion and Deletion Operation on Binary Search Tree with example.

Q.) List the types of Binary Search Tree. Explain Insertion and Deletion Operation on Binary Search Tree with example.
Subject: Data Structures

Binary Search Tree (BST) is a node-based binary tree data structure which has the following properties:

The left subtree of a node contains only nodes with keys lesser than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
The left and right subtree each must also be a binary search tree.

There are three types of Binary Search Trees:

Balanced Binary Search Tree: The difference between heights of left and right subtrees for every node is not more than k (mostly 1). Examples: AVL Tree, Red-Black Tree, Balanced Binary Tree.
Unbalanced Binary Search Tree: The difference between heights of left and right subtrees for a node can be more than 1. Example: Normal Binary Search Tree without any balance.
Degenerate (or pathological) Tree: A Tree where every internal node has one child. Such trees are performance-wise same as linked list.

Insertion Operation in BST

To insert a node in a BST, we can follow the following steps:

Start from root.
Compare the inserting node with root, if less, go left. If more, go right.
If the subtree where the node is to be inserted is empty, insert the node there.
If the subtree is not empty, repeat the process from step 2.

Example: Insert 50, 30, 20, 40, 70, 60, 80 in an empty Binary Search Tree

       50
     /    \
   30      70
  /  \    /  \
20   40  60   80

Deletion Operation in BST

There are three possible cases to consider while deleting a node:

Node to be deleted is a leaf: Simply remove from the tree.

Example: Delete 20 from above BST
```
       50
     /    \
   30      70
     \    /  \
    40  60   80 
```
Node to be deleted has only one child: Copy the child to the node and delete the child

Example: Delete 30 from above BST
```
       50
     /    \
   40      70
         /  \
        60   80 
```
Node to be deleted has two children: Find inorder successor of the node. Copy contents of the inorder successor to the node and delete the inorder successor. Note that inorder predecessor can also be used.

Example: Delete 50 from above BST
```
       60
     /    \
   40      70
             \
              80 
```

The inorder successor is needed only when the right child is not empty. In this particular case, inorder successor can be obtained by finding the minimum value in the right child of the node.