BST — inorder gives sorted order — Hinglish notes

3.4.5 · Coding › Trees

BST KYA hai? (precise foundation)

"BST" mein key word hai Search — ordering invariant isliye exist karta hai taaki hum uske through binary-search kar sakein.

WHY inorder sorted output deta hai

Scratch se derivation (structural induction se proof)

Hum ise sirf assert nahi karte — hum proof ko base case se upar build karte hain.

Base case. Ek empty tree (ya single node) length $\leq 1$ ki list produce karta hai. Length 0 ya 1 ki list trivially sorted hoti hai. ✔

Inductive hypothesis (IH). Maano ki $T$ se chhote kisi bhi BST ke liye (yaani uske subtrees ke liye), inorder ek sorted list deta hai.

Inductive step. Maano $T$ ka root $r$ hai, left subtree $T_{L}$ hai, right subtree $T_{R}$ hai.

IH se, $inorder (T_{L})$ sorted hai, aur BST property se $T_{L}$ mein har key $< r$ hai. Toh: $inorder (T_{L}) is sorted, and its last element < r .$
IH se, $inorder (T_{R})$ sorted hai, aur $T_{R}$ mein har key $> r$ hai. Toh: $inorder (T_{R}) is sorted, and its first element > r .$
Concatenate karo: [ ...sorted, sab < r ] + [r] + [ sab > r, sorted... ]. Left list aur $r$ ke beech ka boundary increasing hai (last $< r$ ). $r$ aur right list ke beech ka boundary increasing hai ( $r <$ first). Yeh kyun matter karta hai: do sorted lists ka concatenation khud sorted hota hai tab hi jab pehle ki last $\leq$ doosre ki first ho — aur humne abhi prove kar diya ki dono joins yeh respect karte hain. ✔

Induction se, kisi bhi BST ka inorder sorted hota hai. $■$

Figure — BST — inorder gives sorted order

HOW karna hai (code, do tarike)

Worked example Recursive inorder

def inorder(node, out):
    if node is None:        # Why? base case infinite recursion rokta hai
        return
    inorder(node.left, out) # L: pehle chhote keys
    out.append(node.key)    # N: self, ab sahi slot mein
    inorder(node.right, out)# R: bade keys baad mein

Yeh order kyun? Inme se koi bhi do lines swap karo toh sortedness toot jaati hai — L,N,R order hi poori baat hai.

Worked example Iterative inorder (explicit stack)

def inorder_iter(root):
    out, stack, cur = [], [], root
    while cur or stack:
        while cur:                # Why? leftmost tak jao = sabse chhota unseen
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()         # sabse chhota available node
        out.append(cur.key)       # N
        cur = cur.right           # phir right jao
    return out

Stack kyun? Yeh "self + right" wala kaam yaad rakhta hai jo humne left mein dive karte waqt postpone kiya tha — bilkul recursion ke call stack ki tarah kaam karta hai.

Worked trace

Tree:

        8
       / \
      3    10
     / \     \
    1   6     14

8 → 3 → 1 tak left dive karo. 1 print karo. 1 ka koi right nahi.
3 pop karo, 3 print karo. Right mein 6 jao, left dive karo (koi nahi), 6 print karo.
8 pop karo, 8 print karo. Right mein 10 jao, left dive karo (koi nahi), 10 print karo, right mein 14 jao, 14 print karo.
Output: 1, 3, 6, 8, 10, 14 — sorted! Kyun? Har node tab print hua jab uska poora chhota-left family print ho chuka tha.

Complexity. Har node ek baar push/pop hota hai → $O (n)$ time. Stack ke liye $O (h)$ space, jahan $h$ height hai ( $O (lo g n)$ agar balanced ho, $O (n)$ worst-case skewed mein).

Reverse fact (Forecast-then-Verify)

Recall Verify

Haan — sorted inorder $⟺$ BST (distinct keys ke saath). Yeh ek clean validation algorithm deta hai: inorder karo, check karo ki har element $>$ pichle se ho. Koi bhi violation mile toh BST nahi hai. Har node pe min/max ranges check karne se zyada clean hai.

Common mistakes (Steel-manned)

Common mistake "Local check kaafi hai: har node ke liye sirf left.key < node < right.key verify karo."

Kyun sahi lagta hai: BST definition dikhne mein local hai (left child chhota, right child bada). Kyun galat hai: rule poore subtrees ke baare mein hai, sirf immediate children ke baare mein nahi. Right subtree mein koi node kisi ancestor se chhota bhi ho sakta hai.

    5
   / \
  3   7
     /
    4   <-- 4 < 5 lekin 5 ke RIGHT subtree mein hai → INVALID

Local check pass karta hai, phir bhi yeh BST nahi hai. Fix: inorder + "strictly increasing" check use karo, jo yeh pakad leta hai kyunki 4, inorder mein 5 ke baad aata.

Flashcards

BST mein har node ko konsi property satisfy karni chahiye?

Uske left subtree mein saare keys chhote hone chahiye, right subtree mein saare keys bade hone chahiye (recursively).

"Inorder" traversal order kya hota hai?

Left, phir Node, phir Right (L, N, R).

BST ka inorder sorted output kyun deta hai?

Kyunki left subtree (sab chhote) node se pehle print hota hai, aur right subtree (sab bade) baad mein — har node pe recursively sach hota hai.

Tree T ke inorder ka recursive equation kya hai?

inorder(T) = inorder(left) + [root] + inorder(right).

Inorder-sorted proof ka base case kya hai?

Ek empty tree ya single node, jo trivially sorted hai (length ≤ 1).

Inorder traversal ki time aur space complexity kya hai?

O(n) time; O(h) space (h = height) stack/recursion ke liye.

Inorder use karke BST validate kaise karte hain?

Inorder run karo aur check karo ki har element strictly pichle se bada ho.

BST validation ke liye sirf immediate children check karna kyun kaafi nahi hai?

Ek subtree mein koi node kisi ancestor ki bound violate kar sakta hai, chahe har parent–child pair theek lage.

Kya converse sach hai: sorted inorder ka matlab BST?

Haan, distinct keys ke liye — sorted inorder ⇔ BST.

Iterative inorder mein explicit stack kya yaad rakhta hai?

Left spine mein neeche dive karte waqt ancestors ke liye postponed "node visit karo + right jao" kaam.

Recall Feynman: ek 12-saal ke bachche ko explain karo

Socho ek family tree mein bacche khade hain jahan har bachcha apne left side wale sabse lamba aur apne right side wale sabse chhota hai. Tum unhe shortest-to-tallest bulana chahte ho. Toh har bachche pe tum kehte ho: "ruko, pehle main tumhare left side wale sabko bulaata hoon (woh chhote hain), phir TUMHE bulaaunga, phir right wale sabko (bade)." Har bachche ke liye yahi karo aur — magic — woh perfect height order mein nikal aate hain. Woh left-me-right rule hi sab kuch hai.

Connections

Binary Search Tree — woh structure jiska invariant yeh power karta hai.
Tree Traversals — preorder/postorder/level-order (jo sort nahi karte).
Validate BST — is fact ka direct application.
Binary Search — arrays par wahi "left chhota, right bada" logic.
Structural Induction — yahan use ki gayi proof technique.
AVL & Red-Black Trees — $h = O (lo g n)$ maintain karte hain taaki traversal fast rahe.
Kth Smallest Element in BST — kth output par inorder jaldi rok do.