BST — inorder gives sorted order: Visual walkthrough

We assume nothing. If you have never seen a tree drawn before, start at Step 1.

Step 1 — What a "tree" even looks like

WHAT. A tree is dots joined by lines, drawn top-down. The top dot is the root. Each dot is a node and holds one number, its key. A node can have a left child (a node hanging down-left) and a right child (down-right). A node with no children is a leaf.

WHY draw it top-down. Because the whole story is about position: "left" and "right" are literally the down-left and down-right lines. The picture is the rule.

PICTURE. Look at the figure. The amber dot at the top is the root. Follow the white line going down-left to reach a left child; down-right to reach a right child.

Figure — BST — inorder gives sorted order

Step 2 — The rule that makes it a Search tree

WHAT. A Binary Search Tree adds one law. For every node $n$ :

$the whole down-left family all keys in n ’s left subtree < the node itself n . key < the whole down-right family all keys in n ’s right subtree$

Read the three pieces: the left group is entirely smaller than $n$ ; $n$ sits in the middle; the right group is entirely larger.

WHY "subtree" and not just "child". This is the trap the parent note warns about. The law is not "left child smaller" — it is "left subtree, every last descendant, smaller." A grandchild two levels down still has to obey.

PICTURE. The node with key $8$ is boxed. Everything in its cyan (left) region is $< 8$ ; everything in its amber (right) region is $> 8$ . Notice the deepest node in the left region is still under $8$ .

Step 3 — The visiting order called "inorder"

WHAT. Traversal means: print every key, each exactly once, in some order. Inorder picks this order at every node:

$inorder = do left subtree L \to print this node N \to do right subtree R$

and inside the left subtree you obey the same L, N, R rule again — it is recursive.

WHY this exact order. Because the BST law says left is smaller, right is larger. If I want small-to-large, I must clearly empty out the smaller side first, print myself, then the larger side. Any other of the six possible orders (like N,L,R) would print me before my smaller family — wrong.

PICTURE. The numbered arrows trace the L→N→R rule at the root only. The "1" arrow dives left, "2" is print-self, "3" dives right.

Step 4 — Base case: the smallest possible trees

WHAT. Before recursion can build big answers, it needs a floor. Two floors:

The empty tree prints nothing → the list [].
A single node prints one number → the list [k].

WHY these are trivially sorted. A list with $0$ or $1$ elements has no pair to compare, so it cannot be out of order. Sortedness is a statement about neighbours; with no neighbours there is nothing to break.

PICTURE. Left: an empty slot, output []. Right: a lone node, output [k]. Both carry a check mark.

This is the anchor of the induction: everything larger is built by gluing these.

Step 5 — The inductive glue: joining two sorted lists

WHAT. Assume (inductive hypothesis) that inorder already returns a sorted list on any tree smaller than $T$ — so on $T_{L}$ and $T_{R}$ . We now glue:

$[sorted, all < r \dots, m] + [the root r] + [sorted, all > r p, \dots]$

Here $m$ is the last (largest) key of the left list; $p$ is the first (smallest) key of the right list.

WHY it stays sorted. A sorted list glued to a sorted list is sorted only if the last of the first $\leq$ the first of the second. Check the two seams:

Left seam: $m < r$ — guaranteed because $m$ lives in the left subtree, which is entirely below $r$ (Step 2). ✔
Right seam: $r < p$ — guaranteed because $p$ lives in the right subtree, entirely above $r$ . ✔

Both seams rise, and the two halves were already internally sorted, so the whole list rises.

PICTURE. The two sorted blocks are cyan (left, all under $r$ ) and amber (right, all over $r$ ), with $r$ in white between them. Two arrows label the seams $m < r$ and $r < p$ — the only two joins that could have failed, both safe.

Step 6 — Running the machine on a real tree

WHAT. Apply Steps 3–5 to the parent note's tree. We chase the L,N,R rule and print each node the moment its entire left family is done.

WHY trace by hand. Because the proof says "it works"; the trace shows why each number lands where it does — every print happens exactly after its smaller-left family, never before.

PICTURE. The tree with a small numbered badge on each node showing the print order. Follow the badges $1, 2, 3, 4, 5, 6$ and read the keys they sit on.

Reading the badges in number order gives you the sorted keys — that is the whole theorem in one glance. (Stop early at badge $k$ and you have the k-th smallest.)

Step 7 — The degenerate case: a skewed tree

WHAT. What if every node has only a right child? The tree is a straight diagonal line — basically already a list.

WHY show it. Edge cases are where confidence dies. Here $T_{L}$ is empty at every node, so inorder is just "print self, go right" repeated — still sorted, and it reveals the space cost: the recursion/stack goes $n$ deep because there is no branching.

PICTURE. A right-leaning chain $1 \to 2 \to 3 \to 4$ . The output list is drawn beside it, identical to the tree read top-to-bottom. A note flags stack depth $= n$ .

The one-picture summary

Everything above compressed: the recursive equation, the two safe seams, and the rising output ribbon, drawn together.

Recall Feynman: retell the whole walkthrough in plain words

Picture a family tree where every person is taller than their whole left branch and shorter than their whole right branch. I want to call names shortest-first. So I stand at the root and say: "Hang on — before I call you, I must call your entire left branch, because they are all shorter." I repeat that promise inside the left branch, and inside its left branch, until I hit someone with no left branch — the shortest person alive. I call them. Then I back up one step and call that person. Then I turn to their right branch and do the same thing. Because "left is shorter" is true at every node, no one is ever called before someone shorter than them. So the names come out in perfect height order — and that is why inorder of a BST is sorted. The only two places a mistake could sneak in are the two seams: me-vs-my-left and me-vs-my-right, and the tree's own rule guarantees both.

Connections

Parent: the theorem — this page is its visual derivation.
Binary Search Tree — the ordering law of Step 2.
Tree Traversals — where inorder sits among the traversals.
Structural Induction — the base-case + glue logic of Steps 4–5.
Validate BST — the mistake in Step 2, turned into an algorithm.
Binary Search — the same left-small/right-big idea on arrays.
AVL & Red-Black Trees — fix the Step 7 skew.
Kth Smallest Element in BST — stop the Step 6 trace early.