BST — inorder gives sorted order — Coding notes

WHAT is a BST? (precise foundation)

The key word in "BST" is Search — the ordering invariant exists precisely so we can binary-search through it.

WHY inorder produces sorted output

Derivation from scratch (proof by structural induction)

We never just assert it — we build the proof from the base case up.

Base case. An empty tree (or a single node) produces a list of length $\le 1$ . A list of length 0 or 1 is trivially sorted. ✔

Inductive hypothesis (IH). Assume for any BST smaller than $T$ (i.e. its subtrees), inorder gives a sorted list.

Inductive step. Let $T$ have root $r$ , left subtree $T_L$ , right subtree $T_R$ .

By IH, $\text{inorder}(T_L)$ is sorted, and by the BST property every key in $T_L$ is $< r$ . So: $\text{inorder}(T_L) \text{ is sorted, and its last element} < r.$
By IH, $\text{inorder}(T_R)$ is sorted, and every key in $T_R$ is $> r$ . So: $\text{inorder}(T_R) \text{ is sorted, and its first element} > r.$
Concatenate: [ ...sorted, all < r ] + [r] + [ all > r, sorted... ]. The boundary between left list and $r$ is increasing (last $< r$ ). The boundary between $r$ and right list is increasing ( $r <$ first). Why this matters: a concatenation of two sorted lists is itself sorted iff the last of the first $\le$ first of the second — and we just proved both joins respect that. ✔

By induction, inorder of any BST is sorted. $\blacksquare$

Figure — BST — inorder gives sorted order

HOW to do it (code, two ways)

Worked example Recursive inorder

def inorder(node, out):
    if node is None:        # Why? base case stops infinite recursion
        return
    inorder(node.left, out) # L: smaller keys first
    out.append(node.key)    # N: self, now in correct slot
    inorder(node.right, out)# R: larger keys last

Why this order? Swapping any two of these three lines breaks the sortedness — the L,N,R order is the whole point.

Worked example Iterative inorder (explicit stack)

def inorder_iter(root):
    out, stack, cur = [], [], root
    while cur or stack:
        while cur:                # Why? dive to leftmost = smallest unseen
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()         # smallest available node
        out.append(cur.key)       # N
        cur = cur.right           # then go right
    return out

Why the stack? It remembers the "self + right" work we postponed while diving left — exactly mimicking the recursion's call stack.

Worked trace

Tree:

        8
       / \
      3    10
     / \     \
    1   6     14

Dive left from 8 → 3 → 1. Print 1. 1 has no right.
Pop 3, print 3. Go right to 6, dive left (none), print 6.
Pop 8, print 8. Go right to 10, dive left (none), print 10, go right to 14, print 14.
Output: 1, 3, 6, 8, 10, 14 — sorted! Why? Each node printed only after its entire smaller-left family.

Complexity. Every node pushed/popped once → $O(n)$ time. Space $O(h)$ for the stack, where $h$ is height ( $O(\log n)$ if balanced, $O(n)$ worst-case skewed).

The reverse fact (Forecast-then-Verify)

Recall Verify

Yes — sorted inorder $\iff$ BST (with distinct keys). This gives a clean validation algorithm: do inorder, check each element $>$ previous. If any violation, it's not a BST. Cleaner than checking min/max ranges at every node.

Common mistakes (Steel-manned)

Common mistake "Local check is enough: just verify left.key < node < right.key for each node."

Why it feels right: the BST definition looks local (left child smaller, right child bigger). Why it's wrong: the rule is about entire subtrees, not immediate children. A node deep in the right subtree could still be smaller than an ancestor.

    5
   / \
  3   7
     /
    4   <-- 4 < 5 but sits in 5's RIGHT subtree → INVALID

Local check passes, yet it's not a BST. Fix: use inorder + "strictly increasing" check, which catches this because 4 would appear after 5.

Flashcards

What property must every node satisfy in a BST?

All keys in its left subtree are smaller, all keys in its right subtree are larger (recursively).

What traversal order is "inorder"?

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

Why does inorder of a BST give sorted output?

Because left subtree (all smaller) is printed before the node, and right subtree (all larger) after — recursively true at every node.

What is the recursive equation for inorder of tree T?

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

What is the base case of the inorder-sorted proof?

An empty tree or single node, which is trivially sorted (length ≤ 1).

Time and space complexity of inorder traversal?

O(n) time; O(h) space (h = height) for the stack/recursion.

How do you validate a BST using inorder?

Run inorder and check each element is strictly greater than the previous.

Why is checking only immediate children insufficient for BST validation?

A node deep in a subtree can violate an ancestor's bound even if every parent–child pair looks fine.

Is the converse true: sorted inorder implies BST?

Yes, for distinct keys — sorted inorder ⇔ BST.

What does the explicit stack in iterative inorder remember?

The postponed "visit node + go right" work for ancestors while we dive down the left spine.

Recall Feynman: explain to a 12-year-old

Imagine kids lined up in a family tree where every kid is taller than everyone on their left and shorter than everyone on their right. You want to call them out shortest-to-tallest. So at each kid you say: "wait, let me first call everyone on your left side (they're shorter), then call YOU, then call everyone on your right (taller)." Do this for every kid and — magic — they come out in perfect height order. That left-me-right rule is all you need.

Connections

Binary Search Tree — the structure whose invariant powers this.
Tree Traversals — preorder/postorder/level-order (which do not sort).
Validate BST — direct application of this fact.
Binary Search — same "left smaller, right bigger" logic on arrays.
Structural Induction — the proof technique used here.
AVL & Red-Black Trees — keep $h=O(\log n)$ so traversal stays fast.
Kth Smallest Element in BST — stop inorder early at the kth output.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, BST (Binary Search Tree) ka rule simple hai: har node ke left mein chhote keys aur right mein bade keys hote hain — aur yeh rule recursively poore subtree pe lagta hai, sirf turant wale child pe nahi. Yahi cheez "Search" word ko meaning deti hai.

Ab inorder traversal ka order hai Left → Node → Right (L, N, R). Matlab kisi bhi node pe khade ho, pehle uske saare chhote (left) waale print karo, phir khud ko, phir saare bade (right). Jab har node pe yehi karte ho, toh output apne aap chhote se bade order mein aata hai — sorted! Isko hum induction se prove karte hain: empty/single node toh trivially sorted, aur agar left aur right subtree sorted hain aur root unke beech mein fit hota hai (last-left < root < first-right), toh poora list bhi sorted.

Ek bahut common galti: log sochte hain ki sirf left.key < node < right.key check karna kaafi hai BST validate karne ke liye. Yeh galat hai — deep node ancestor ka bound tod sakta hai. Best trick: inorder chalao aur check karo har element pichle se strictly bada hai ya nahi. Agar kahin nahi, toh BST nahi hai.

Yaad rakhne ka tareeka: "Inorder Rises" — L, N, R se values badhti hain. Time complexity $O(n)$ , space $O(h)$ height ke barabar. Yehi concept aage Kth smallest element aur Validate BST jaise problems mein direct use hota hai, isliye master kar lo.

BST — inorder gives sorted order

WHAT is a BST? (precise foundation)

WHY inorder produces sorted output

Derivation from scratch (proof by structural induction)

HOW to do it (code, two ways)

Worked trace

The reverse fact (Forecast-then-Verify)

Common mistakes (Steel-manned)

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Trees

Connections