BST — inorder gives sorted order: Worked examples

You have already met the big idea in the parent note: in a Binary Search Tree, visiting Left → Node → Right (inorder) spits keys out in increasing order. This page does one job: it walks every kind of tree you could be handed and traces the traversal by hand, so no shape ever surprises you.

Before we trace anything, let us agree on the plain-word meaning of the words we will use, because we will use them a LOT.

The scenario matrix

Here is the full list of shapes a BST-inorder question can be. Every worked example below is tagged with the cell it covers, so by the end every row is ticked.

#	Case class	What makes it tricky	Covered by
A	Empty tree (0 nodes)	Degenerate — output must be `[]`	Ex 1
B	Single node	Base case of the proof	Ex 1
C	Balanced tree, both children everywhere	The "normal" case	Ex 2
D	Left-skewed (only left children)	Looks like a linked list going down-left	Ex 3
E	Right-skewed (only right children)	Linked list going down-right	Ex 3
F	Negative & mixed-sign keys	Ordering must respect number line, not size	Ex 4
G	Duplicate keys present	Strict `<` policy — where does the twin go?	Ex 5
H	"Is it even a BST?" (validation)	A deep node violates a far ancestor	Ex 6
I	Real-world word problem	Translate a story into left/right	Ex 7
J	Exam twist — stop early (Kth smallest)	Don't finish the whole traversal	Ex 8

Case A & B — the degenerate floor

Case C — the balanced everyday tree

Figure — BST — inorder gives sorted order

Worked example A full balanced tree (cell C)

Trace inorder on the tree drawn above:

        50
       /  \
     30    70
    /  \   /  \
   20  40 60  80

Forecast: the keys are 20,30,40,50,60,70,80. Predict the output order — does inorder just read them left-to-right off the picture? (Hint: look at the bottom row order in the figure.)

Step 1 — dive to the leftmost. Why this step? The smallest key is always the leftmost node. From 50 → 30 → 20. Print 20. What it looks like: the blue arrow in the figure walking down the left spine.

Step 2 — climb one, print the parent, then its right child. Why this step? After a node's whole left family is done, the node itself is next (N), then we service its right (R). Back at 30, print 30; go right to 40 (no left), print 40.

Step 3 — climb to the root. Why? 30's whole subtree is exhausted, so 50 is next. Print 50.

Step 4 — repeat the same L-N-R on the right half. Why? The right subtree is itself a BST, so the same rule applies. 70's left is 60 → print 60, then 70, then 80.

Output: 20, 30, 40, 50, 60, 70, 80.

Verify: Each printed value is strictly greater than the one before (20<30<40<50<60<70<80). ✔ Notice inorder did not read the bottom row left-to-right (20,40,60,80) — it interleaves parents in.

Cases D & E — the two skewed sticks

Worked example Left-skewed and right-skewed trees (cells D, E)

(i) Left-skewed: 5 → 4 → 3 → 2 → 1 where each node's only child is its left child. (ii) Right-skewed: 1 → 2 → 3 → 4 → 5 where each node's only child is its right child.

Forecast: both are valid BSTs shaped like a line. Do they produce the same sorted output? Guess yes/no.

Step 1 — trace the left-skew. Why this step? With only left children, we dive all the way down first: 5→4→3→2→1. The first thing printed is the deepest, 1. Then we pop back up printing each: 2, 3, 4, 5 (each has no right child, so nothing between). Output: 1, 2, 3, 4, 5. What it looks like: the left panel of the figure — one long diagonal, stack depth h = 5.

Step 2 — trace the right-skew. Why this step? With only right children, each node has an empty left subtree, so it prints immediately on arrival: 1, go right, 2, right, 3, 4, 5. Output: 1, 2, 3, 4, 5.

Verify: identical sorted lists ✔ — but the cost differs in space. Left-skew forces the stack to hold all 5 nodes at once ( $O (h) = O (n)$ ); right-skew never holds more than 1. Both are $O (n)$ time. This is the worst-case $h = n$ that balanced trees exist to prevent.

Case F — negatives and mixed signs

Worked example Keys crossing zero (cell F)

Trace inorder on:

         0
       /   \
    -5      7
    /  \      \
  -8   -1      9

Forecast: "smaller" here means further left on the number line, so -8 is the smallest, not 8. Predict the output.

Step 1 — leftmost = most negative. Why this step? Diving left, 0 → -5 → -8. The BST rule orders by value, and -8 < -5 < 0. Print -8.

Step 2 — back up. Why? Pop -5's subtree in L-N-R: after -8 print -5, then its right child -1 (which is still < 0 ✔, that's why it's left of 0's subtree).

Step 3 — root then right half. Why? All negatives done, print 0, then the right subtree 7, 9: print 7, then 9.

Output: -8, -5, -1, 0, 7, 9.

Verify: -8 < -5 < -1 < 0 < 7 < 9 — strictly increasing on the number line ✔. Sign never breaks the logic; only the < comparison matters.

Case G — duplicate keys

Worked example What happens with a twin key (cell G)

Suppose your insert policy is "equal keys go to the right subtree". Insert 4, 2, 6, 4 in that order and inorder-trace it.

Forecast: where does the second 4 land, and will the output be strictly increasing or have an equal pair?

Step 1 — build the tree. Why this step? We must see the shape before we trace. Insert 4 (root). Insert 2 (< 4, left). Insert 6 (> 4, right). Insert the second 4: policy says equal → go right of the first 4, so it goes down 4's right toward 6; 4 < 6 so it becomes 6's left child.

Step 2 — trace inorder. Why? Standard L-N-R. Leftmost of root is 2 → 2. Root → 4. Right subtree: 6's left is the twin 4 → 4, then 6. Output: 2, 4, 4, 6.

Verify: the output is non-decreasing (2 ≤ 4 ≤ 4 ≤ 6) but not strictly increasing — the two 4's are adjacent. So a validator must use <= if duplicates are allowed, and strict < if they are forbidden. This is the exact trap in the parent's third [!mistake]. ✔

Case H — the sneaky invalid tree

Worked example Validate by inorder, catch the deep violator (cell H)

Is this a valid BST?

Forecast: every parent–child pair looks legal (5<10, 15>10, 6<15, 20>15). Predict whether the local check passes — and whether the tree is actually valid.

Step 1 — run the local (child-only) check. Why this step? To show it is fooled. 5<10 ✓, 15>10 ✓, 6<15 ✓, 20>15 ✓. Local check says "valid". But 6 lives in 10's right subtree, so it must be > 10 — and 6 < 10. Violation, unseen locally.

Step 2 — run inorder instead. Why? Because sorted-inorder ⇔ BST catches global violations. Trace: 5, 10, then right subtree of 10 → leftmost is 6 → 6, then 15, 20. Output sequence: 5, 10, 6, 15, 20.

Step 3 — scan for a drop. Why? A valid BST's inorder is strictly increasing. Here 10 is followed by 6 — a decrease. So prev < cur fails at that step.

Verify: the check flags position where 6 < 10 (prev=10, cur=6). Tree correctly declared NOT a BST ✔. See the red arrow in the figure marking the illegal 6.

Case I — a real-world word problem

Worked example Library shelf ordering (cell I)

A librarian stores books by ID in a BST as they arrive: 500, 200, 800, 100, 300. She wants a shelf list from smallest to largest ID. Which traversal, and what is the list?

Forecast: insertion order is scrambled. Predict the sorted shelf list.

Step 1 — build the BST from arrival order. Why this step? The tree's shape depends on insertion order. 500 root; 200<500 left; 800>500 right; 100<200 left-left; 300>200 but <500 so right of 200.

Step 2 — pick the traversal. Why inorder and not preorder/postorder? Only inorder (L,N,R) guarantees increasing order on a BST — the whole point of this topic. Preorder would give 500,200,100,300,800 (root-first, not sorted).

Step 3 — trace inorder. Leftmost: 500→200→100 → 100, back to 200, its right 300, back to root 500, then 800. Output: 100, 200, 300, 500, 800.

Verify: 100<200<300<500<800 — a correctly sorted shelf list ✔, delivered in $O (n)$ without any extra sorting step.

Case J — the exam twist: stop early

Worked example Kth smallest without finishing (cell J)

In the balanced tree of Example 2 (20,30,40,50,60,70,80), find the 3rd smallest key, but stop the traversal the moment you have it.

Forecast: inorder emits smallest-first, so the k-th value emitted is the k-th smallest. Predict how many nodes you must print before stopping.

Step 1 — inorder emits ascending. Why this step? Because L-N-R prints all-smaller before a node, the sequence of prints is 20 (1st), 30 (2nd), 40 (3rd), …. So a counter that increments on each print tells us our rank.

Step 2 — count and halt. Why halt? We only need the 3rd. Print 20 (count 1), 30 (count 2), 40 (count 3) → count == k, return 40 immediately. We never touch 50, 60, 70, 80.

Answer: 3rd smallest = 40.

Verify: the full sorted list is 20,30,40,50,60,70,80; index 3 (1-based) is 40 ✔. Early stop makes this $O (h + k)$ instead of $O (n)$ — the idea behind Kth Smallest Element in BST.

Recall One-line summary of the whole matrix

Whatever the shape — empty, skewed, negative, duplicated, invalid, or story-dressed — inorder's job is always the same: ::: walk L-N-R, and every node prints only after its entire smaller-left family, so the output rises (or, on an invalid tree, fails to rise and betrays the violation).

Connections

Parent topic — the theory these examples exercise.
Binary Search Tree — the invariant every trace relies on.
Tree Traversals — why preorder/postorder do not sort (see Ex 7).
Validate BST — Case H made concrete.
Kth Smallest Element in BST — Case J's early-stop trick.
AVL & Red-Black Trees — fix the skew cost of Case D/E.
Structural Induction — proves the base case of Ex 1.
Binary Search — same left-smaller/right-bigger logic on arrays.