Lesson 2 � Beginner

BST: Search, Insert, Delete

Binary Search Tree (BST) binary tree ka ek special version hai jismein ek property hoti hai � left subtree mein sab values root se chhoti hain aur right subtree mein sab badi. Ye property BST ko search operations ke liye super efficient banati hai.

? 22 min✓ Beginner✓ Binary Tree basics

BST Property kya hai?

WHAT

BST ki fundamental property: har node ke left subtree mein sirf usse chhoti values hain, aur right subtree mein sirf badi values. MATLAB left.val < root.val < right.val. Ye property recursively har subtree ke liye apply hoti hai.

WHEN

Jab frequently search, insert, aur delete karna ho. BST average case mein O(log n) time deta hai. Arrays mein search O(n) hota hai, BST mein O(log n). Sorted data chahiye toh BST se inorder traversal nikalo.

WHERE

Databases mein indexing, sets aur maps implement karne mein, file systems mein, aur interview mein bahut common hai. BST se related 20+ LeetCode problems hain.

Mental Model: Imagine karo ek library mein books arranged hain. Agar sab books alphabetical order mein hain toh tum quickly kisi book ko dhundh sakte ho � "M" se start karo, agar tumhara letter "M" se chhota hai toh left jao, bada hai toh right jao. BST bhi exactly aise kaam karta hai!

# BST Visual:
# 50
# / \
# 30 70
# / \ / \
# 20 40 60 80

# BST Property verify karo:
# 50 ke left mein: 30, 20, 40 (sab < 50) ?
# 50 ke right mein: 70, 60, 80 (sab > 50) ?
# 30 ke left mein: 20 (< 30) ?
# 30 ke right mein: 40 (> 30) ?
# ... aur sab nodes ke liye same!

BST Search Operation

Search BST ki sabse powerful property hai. Har step mein humari search range aadhi ho jaati hai � bilkul binary search jaisa!

def search(root, val):
 if root is None:
 return None
 
 if root.val == val:
 return root # Mil gaya!
 
 if val < root.val:
 return search(root.left, val) # Left mein dhundho
 else:
 return search(root.right, val) # Right mein dhundho

# Search ka time complexity: O(h) � h = height
# Average: O(log n), Worst: O(n) (skewed tree)

Why Fast? Har comparison ke baad humari search space aadhi ho jaati hai. 16 nodes mein sirf 4 comparisons (log216 = 4). Arrays mein 16 elements mein bhi worst case 16 comparisons lag sakte hain!

BST Insert Operation

Insert karna search jaisa hai � pehle jahan value honi chahiye wahan dhundho, phir wahan naya node bana do. Duplicate values generally ignore ya right subtree mein rakhte hain.

def insert(root, val):
 if root is None:
 return Node(val)
 
 if val < root.val:
 root.left = insert(root.left, val)
 else:
 root.right = insert(root.right, val)
 
 return root

# BST build karna
root = None
for val in [50, 30, 70, 20, 40, 60, 80]:
 root = insert(root, val)

Key Insight: Insert mein hum hamesha leaf node pe jaake naya node add karte hain. Kabhi bhi beech mein node nahi insert hota. Isliye BST mein order matters � agar sorted array se insert karoge toh skewed tree banega (worst case O(n)).

BST Delete Operation

Delete sabse interesting hai. 3 cases hain depending on node kitne children rakhta hai:

def delete(root, val):
 if root is None:
 return root
 
 if val < root.val:
 root.left = delete(root.left, val)
 elif val > root.val:
 root.right = delete(root.right, val)
 else:
 # Node mila � ab delete karo
 
 # Case 1: Leaf node (koi child nahi)
 if root.left is None and root.right is None:
 return None
 
 # Case 2: Ek child hai
 if root.left is None:
 return root.right
 if root.right is None:
 return root.left
 
 # Case 3: Dono children hain
 # Inorder successor dhundho (right subtree ka value)
 successor = find_min(root.right)
 root.val = successor.val
 root.right = delete(root.right, successor.val)
 
 return root

def find_min(node):
 while node.left:
 node = node.left
 return node

Case 1: Leaf Node

Agar node koi child nahi rakhta toh seedha delete karo � None return karo. Sabse easy case.

Case 2: Ek Child

Agar sirf ek child hai toh us child ko return karo � parent seedha usse link ho jayega. Node effectively hat jaata hai.

Case 3: Dono Children

Sabse tricky! Inorder successor (right subtree ka sabse chhota node) se value replace karo, phir successor ko delete karo. BST property maintain rahegi.

Inorder Successor kya hai? Delete karne wale node ke right subtree ka sabse chhota node. Ye uska immediate "next bigger" value hota hai. Isse replace karne se BST property (left < root < right) maintain rahegi.

Time Complexity

# BST Operations Time Complexity:
# Average Case Worst Case
# Search: O(log n) O(n)
# Insert: O(log n) O(n)
# Delete: O(log n) O(n)

# Worst case kab hota hai?
# Jab tree skewed ho � bilkul linked list jaisa
# [1, 2, 3, 4, 5] sirf right children mein
# Toh height = n, search = O(n)

# Solution✓ Balanced BST (AVL, Red-Black Tree)
# jo height ko O(log n) guarantee karte hain

Try it: code khud likho

Exercise

Question: BST mein root = Node(50), insert(root, 30), insert(root, 70), insert(root, 20). Ab search(root, 20) call karo toh kitne comparisons lagenge✓ Sirf number daalo.

Question: [5, 3, 7, 2, 4, 6, 8] values se BST banao. Inorder traversal ka output kya hoga✓ Answer mein space-separated numbers daalo.

Common mistakes

Skewed tree banana: Agar sorted values se BST build karoge ([1,2,3,4,5] se insert) toh tree skewed hoga � bilkul linked list jaisa. Random order ya balancing use karo.
Root change handle karna: Delete operations mein root change ho sakta hai. Hamesha root = delete(root, val) karo, sirf delete(root, val) nahi.
Successor finding bhoolna: Delete mein Case 3 ke liye inorder successor dhundhna zaroori hai. Bina successor ke BST property toot jaayegi.
Duplicate values: BST mein duplicates handle karna tricky hai. Generally ya toh ignore karo ya ek convention fix karo (duplicates right mein jayenge).

Lesson complete?

BST samajh aa gaya✓ Ab tree ke height, diameter, aur balanced tree check karna seekhte hain � ye important interview topics hain.