Binary Search Tree (BST): Insertion and Deletion Operations

BST me insertion aur deletion operations structure ki BST invariant property (left < root < right) ko hamesha preserve karte hain.

1. BST Insertion – O(h)

Naya node hamesha ek Leaf Node ke roop me attach hota hai. Hum root se compare karte hue niche traverse karte hain jab tak sahi NULL pointer na mil jaye.

INSERT_BST(root, val)
1. If root == NULL: Return createNode(val)
2. If val < root->data:
       root->left = INSERT_BST(root->left, val)
3. Else if val > root->data:
       root->right = INSERT_BST(root->right, val)
4. Return root

2. BST Deletion (3 Cases)

Node deletion BST ka sabse conceptual algorithm hai:

Case 1: Node to delete is a LEAF (0 children)
-> Simply remove the node and set parent's pointer to NULL.

Case 2: Node has EXACTLY 1 CHILD
-> Bypass the node: Parent directly points to the child of the deleted node.

Case 3: Node has 2 CHILDREN (Complex Case)
-> Find Inorder Successor (Smallest node in Right Subtree)
   OR Inorder Predecessor (Largest node in Left Subtree).
-> Copy successor's value into the target node.
-> Delete the successor node from the right subtree (which will have at most 1 child).

Agli post me hum cover karenge AVL Tree: Concept and Balance Factor jo BST ke worst-case O(n) ko permanently eliminate karta hai.