BST — inorder gives sorted order: Foundations

Before you can understand "inorder gives sorted order," you must own a handful of small ideas. We build them one at a time, each resting on the previous. Nothing is assumed.

1. What is a node? (the atom)

Picture one box with the number inside and two arrows dangling below it.

Figure — BST — inorder gives sorted order

Why we need it. A tree is made of nodes. If the atom is fuzzy, everything above it collapses. The value inside we will call the node's key; the two arrows are left and right.

2. Arrows that point to nothing — None / empty

Picture: an arrow with a small dot at the end and no box attached.

Why we need it. Every walk of a tree eventually runs off the bottom. "None" is how we notice we've run out — it is the stopping signal (the base case) in every algorithm here. Without a name for "nothing," recursion never halts.

3. Parent, child, root, leaf, subtree

Why we need "subtree" most of all. The BST rule is not about a node's immediate children — it is about a node's entire left subtree and entire right subtree. Miss this word and you fall for the classic mistake (a distant descendant breaking the rule while every parent–child pair looks fine).

4. The comparison symbols $<$ and $>$

Picture: a horizontal number line; smaller values live left, larger live right.

Why we need it, and why strict. The BST rule uses strict inequalities: left subtree keys are strictly $<$ the node, right subtree keys strictly $>$ . We assume all keys are distinct (no repeats), so we never need $\leq$ or $\geq$ . This is the exact reason the sorted-output check later uses prev < cur and not prev <= cur.

5. The BST ordering invariant — assembled

Now stack the pieces. Take a node; look at its whole left subtree and whole right subtree using $<$ and $>$ :

Picture: the whole left cloud is entirely below the node's value; the whole right cloud is entirely above it.

Why "invariant"? An invariant is a promise that stays true at every node, everywhere in the tree, forever. That everywhere-ness is what lets a single recursive walk trust the same fact at each step. See Binary Search Tree for the full structure and Binary Search for the same left-small / right-big logic on flat arrays.

6. Recursion — a rule that calls itself

Picture: the subtree figure again — a tree contains smaller trees, so "walk the tree" naturally becomes "walk the left tree, do me, walk the right tree."

Why we need it. Both the traversal and its proof are recursive. The base case is the empty tree (§2); the reduction is "solve for the two subtrees." This is exactly the shape of Structural Induction, the proof technique the parent note uses.

7. Traversal and the notation $L, N, R$

Why this exact order. Left holds the smaller family, right holds the larger. Printing $L$ then $N$ then $R$ pours out smaller → self → larger at every level — which is precisely sorted. Other orders exist (preorder $N, L, R$ ; postorder $L, R, N$ ) and do not sort; see Tree Traversals.

8. The list-building symbols: $+$ (concatenation) and $[\cdot]$

Why we need it. The parent's master equation is written with these symbols: $inorder (T) = inorder (T_{L}) + [root] + inorder (T_{R})$ Here $T$ is the whole tree, $T_{L}$ its left subtree, $T_{R}$ its right subtree. Read it as: the sorted output is (left's output) then (the root) then (right's output). Every symbol in that line is now something you defined yourself. This is also the doorway to Kth Smallest Element in BST (stop the walk after $k$ items) and Validate BST (check the output is increasing).

Prerequisite map

Equipment checklist

Answer each before moving to the parent note. Reveal to self-check.

I can draw a single node with its key and two arrows

Yes — a box holding a value plus a left arrow and a right arrow, each possibly pointing to None.

I know what None means and where it appears

It is an arrow pointing to nothing; it marks the empty tree and is the base case that stops recursion.

I can name the root, a leaf, and point to a subtree in a drawing

Root = top node (no parent); leaf = node with both arrows None; subtree = any node plus everything hanging below it.

I understand why "subtree" (not "child") is the key word in the BST rule

The rule constrains every key in the entire left/right subtree, so a distant descendant can violate it even if each parent–child pair looks fine.

I can read

a < b

and

a > b

and say why they are strict here

a < b

a

smaller (left on number line); strict because keys are distinct, so no

\leq

I can state the BST invariant in symbols

For every node

n

: all left-subtree keys

< n . key <

all right-subtree keys, recursively.

I can explain recursion's base case and reduction for a tree

Base case = empty tree; reduction = solve the left subtree and right subtree, both smaller versions of the same problem.

I know what

L, N, R

means and why it sorts

Left, Node, Right — outputs smaller family, then self, then larger family, at every level = sorted.

I can read

inorder (T_{L}) + [root] + inorder (T_{R})

Left's sorted output, then a one-element list holding the root, then right's sorted output, stuck end to end.

Connections

Binary Search Tree — the full structure these foundations describe.
Tree Traversals — preorder/postorder use the same node atoms, different order.
Validate BST — uses the strict-increasing idea built in §4.
Binary Search — same left-smaller / right-larger comparison logic on arrays.
Structural Induction — the recursion of §6 turned into a proof.
AVL & Red-Black Trees — keep the tree shallow.
Kth Smallest Element in BST — reads the sorted walk and stops early.
3.4.05 BST — inorder gives sorted order (Hinglish) — same content in Hinglish.