Binary Search Tree (BST) — BST property, insert, search, delete (3 cases)

3.4.4 · Coding › Trees

BST property KYUN exist karti hai?

KYNA chahiye: ek data structure jo search, insert, delete sab fast support kare (ideally $O (lo g n)$ ), aur dynamic rahe (sizes change hote rahein).

Ek sorted array $O (lo g n)$ search deta hai (binary search) lekin $O (n)$ insert/delete (shifting ki wajah se).
Ek linked list $O (1)$ insert deta hai lekin $O (n)$ search.

Property KYUN help karti hai: Agar hum "left < node < right" ka invariant maintain karein, toh kisi bhi node par hum ek comparison se direction decide kar sakte hain. Left ya right jaane par poora ek subtree discard ho jaata hai. Agar tree balanced hai, depth $lo g n$ hai, toh saare operations $O (lo g n)$ cost karte hain.

Figure — Binary Search Tree (BST) — BST property, insert, search, delete (3 cases)

Search — property se derive karo

def search(node, t):
    while node is not None:
        if t == node.key:
            return node
        node = node.left if t < node.key else node.right
    return None      # not present

Yeh step KYUN? Har comparison invariant use karta hai aur ek poora subtree eliminate karta hai, isliye hum ek single root-to-leaf path follow karte hain. Cost = path length = $O (h)$ jahan $h$ = height.

Insert — search karo, phir khaali jagah par attach karo

def insert(root, v):
    if root is None:
        return Node(v)
    if v < root.key:
        root.left = insert(root.left, v)
    elif v > root.key:
        root.right = insert(root.right, v)
    # v == root.key: duplicate, ignore (ya apni marzi se handle karo)
    return root

Yeh step KYUN? Hum exactly search ki tarah utarte hain, jaate waqt invariant preserve karte hain. Naye nodes hamesha leaves ki tarah insert hote hain, isliye koi existing relationship nahi tootati. Cost $O (h)$ .

Delete — 3 cases (BSTs ka dil)

Pehle node dhoondho. Phir children ki sankhya ke hisaab se handle karo.

def find_min(node):          # leftmost node
    while node.left is not None:
        node = node.left
    return node
 
def delete(root, v):
    if root is None:
        return None
    if v < root.key:
        root.left = delete(root.left, v)
    elif v > root.key:
        root.right = delete(root.right, v)
    else:                                # found node to delete
        if root.left is None:            # Case 1 & 2 (no left child)
            return root.right
        if root.right is None:           # Case 2 (no right child)
            return root.left
        succ = find_min(root.right)      # Case 3: in-order successor
        root.key = succ.key              # copy successor key up
        root.right = delete(root.right, succ.key)  # delete successor
    return root

Yeh step KYUN?

return root.right jab koi left child nahi cleanly leaf (dono None → None return karta hai) aur one-child cases cover karta hai. Elegant unification.
Case 3 mein successor right subtree ka leftmost node hota hai, isliye uske paas no left child → use delete karna hamesha Case 1 ya 2 hai. Recursion kabhi infinite loop nahi karega.

BST-validation mistake ko steel-man karna

Common mistake "Bas har node ko uske do children se check karo"

KYUN sahi lagta hai: property batayi jaati hai children ke terms mein (left.key < key < right.key), isliye sirf children check karna kaafi lagta hai. Counter-example:

       10
      /  \
     5    15
         /
        6      <-- 6 < 10 lekin yeh RIGHT subtree mein hai!

Har node local child check pass karta hai, phir bhi 6 ancestor 10 ke saath property violate karta hai. Fix: range ke saath validate karo: har node ko $(l o w, hi g h)$ mein hona chahiye; left pe $hi g h = k ey$ ke saath recurse karo, right pe $l o w = k ey$ ke saath.

def is_bst(node, low=float('-inf'), high=float('inf')):
    if node is None: return True
    if not (low < node.key < high): return False
    return is_bst(node.left, low, node.key) and \
           is_bst(node.right, node.key, high)

Active recall

Recall Pehle predict karo, phir dekho

Left/right jaana aadha kaam KYUN discard karta hai?
Naya inserted key hamesha kahan rakha jaata hai?
Case 3 mein in-order successor ke paas zyada se zyada 1 child hi KYUN hota hai?
Worst-case height kya hai aur kab hota hai?

Answers: (1) invariant guarantee karta hai ki target sirf ek side par ho sakta hai; (2) ek leaf ki tarah; (3) yeh right subtree ka leftmost node hai, isliye uske paas left child nahi hota; (4) $n - 1$ , jab keys sorted/reverse-sorted order mein insert ki jaayein (degenerate stick).

Recall Feynman: ek 12-saal ke bachche ko samjhao

Ek guessing game socho jahan numbers shelves par rakhi hain. Har shelf par ek number hai. Chhote numbers left wali shelf par jaate hain, bade right par — aur yeh rule har shelf ke liye repeat hota hai. Koi number dhoondhne ke liye upar se shuru karo aur hamesha poochho "chhota hai ya bada?", left ya right kadam rakhte hao. Har kadam par tum shelves ka ek poora dhera skip karte ho, isliye bahut jaldi mil jaata hai. Ek aisi shelf hatane ke liye jiske saath do shelves lagi hain, tum agla bada number right side se secretly le aate ho uski jagah lene, kyunki wahi ek number hai jo sab ko sahi order mein rakhta hai.

Flashcards

BST property kya hai (precisely batao)?

Har node ke liye, uske left subtree ke saare keys strictly chhote hain, aur right subtree ke saare keys strictly bade hain node ki key se — recursively har node ke liye.

Kaun si traversal BST ko sorted order mein deti hai?

In-order (left, node, right) strictly increasing keys deta hai.

BST search

O (h)

KYUN hai,

O (lo g n)

guaranteed nahi?

Hum ek root-to-leaf path follow karte hain jiska length = height

h

hai;

h

sirf tab

lo g n

hota hai jab tree balanced ho, warna

n - 1

tak ho sakta hai.

BST mein naya key kahan insert hota hai?

Hamesha ek naye leaf ki tarah, us jagah jahan us key ki search tree se "girna" (None hit karna) hoti hai.

Delete Case 1 (leaf)?

Node remove karo; parent ka pointer None set karo.

Delete Case 2 (ek child)?

Splice it out — node ke single child ko directly parent se connect karo.

Delete Case 3 (do children)?

Node ki key ko uske in-order successor (right subtree ka min) se replace karo, phir us successor node ko delete karo, jiske paas ≤1 child hai.

Case 3 mein successor ke paas zyada se zyada ek child hi KYUN hota hai?

Yeh right subtree ka leftmost node hai, isliye uske paas left child nahi hota.

Sirf direct children check karna BST validate KYUN nahi karta?

Ek node apne parent ko satisfy kar sakta hai lekin kisi door ke ancestor ki range violate kar sakta hai; tumhe neeche propagate hone wali value ranges check karni padti hain.

BST

O (n)

operations mein KYUN degenerate hota hai?

Jab keys (reverse-)sorted order mein insert ki jaayein, ek linear "stick" banta hai; self-balancing (AVL/Red-Black) se fix hota hai.

Right subtree wale node ka in-order successor KAISE dhoondhein?

Ek baar right jaao, phir left child na milne tak baar baar left jaate raho (right subtree ka find_min).

Connections

Binary Tree — terminology & traversals (in-order BST ka sorted walk hai)
Binary Search on Sorted Array (same halving idea, static data)
AVL Tree aur Red-Black Tree (degenerate BSTs ke liye self-balancing fix)
Tree Height vs Depth (KYUN $h$ saari costs drive karta hai)
Heap vs BST (heap parent–child ko priority se order karta hai, left/right ko value se nahi)
Recursion on Trees (delete/insert as return-the-subtree pattern)