3.4.5 · D5Trees
Question bank — BST — inorder gives sorted order
Parent topic: BST — inorder gives sorted order · Hinglish: 3.4.05 BST — inorder gives sorted order (Hinglish)
True or false — justify
Inorder traversal of ANY binary tree returns a sorted list.
False. Inorder always visits Left–Node–Right, but sortedness comes from the BST ordering invariant. On a non-BST tree you get some permutation, not a sorted one.
For a valid BST with distinct keys, sorted inorder output is guaranteed.
True. Left subtree (all smaller) prints before the node, right subtree (all larger) after — recursively, so the concatenation is strictly increasing.
If inorder output is strictly increasing, the tree must be a BST (distinct keys).
True. This is the converse and it holds: sorted inorder ⇔ BST for distinct keys, which is exactly why BST validation can just run inorder and check
prev < cur.Preorder traversal of a BST also gives sorted order.
False. Preorder is Node–Left–Right, so it prints the root before its smaller left family. Only inorder (L,N,R) rises.
Checking left.key < node.key < right.key at every node correctly validates a BST.
False. That only checks immediate children. A node deep in a subtree can violate a distant ancestor's bound while every parent–child pair looks fine.
A tree that is a single node is a valid BST.
True. A one-node tree has empty subtrees, so both "all left < node" and "all right > node" hold vacuously — it is the base case of the induction.
An empty tree is a valid BST.
True. There are no keys to violate any rule, so the property holds vacuously; inorder returns the empty (trivially sorted) list.
Using prev <= cur (instead of <) in an inorder validity check is always safe.
False. With
<= you wrongly accept equal adjacent keys. For a strict BST with distinct keys you need prev < cur; the choice depends on your duplicate policy.Two different BST shapes can produce the same inorder output.
True. Many differently-shaped BSTs hold the same set of keys, and all of them inorder to the same sorted sequence — the shape encodes structure, the inorder erases it.
Iterative inorder needs the same asymptotic space as recursive inorder.
True. Both use space — the explicit stack mirrors exactly the call stack the recursion would build.
Inorder traversal of a balanced BST is faster asymptotically than on a skewed one.
False. Both are time since every node is visited once. Only the space differs: balanced vs skewed.
Spot the error
"To validate a BST, I recursively check that each node's left child is smaller and right child is larger." — what's the flaw?
It's a local check. It misses violations by descendants, e.g. a node in the right subtree that is smaller than the root but larger than its own parent.
"Inorder sorts the tree, so I can sort any array by inserting into a binary tree then inorder-ing." — what's missing?
You must insert maintaining the BST invariant (each key goes left/right by comparison). Inserting arbitrarily builds a non-BST, and then inorder does not sort.
"My validity check compares each node only to its parent's key." — why can it pass an invalid tree?
A right-child that is smaller than a grandparent is illegal but still larger than its own parent, so a parent-only check accepts it.
Consider this tree; the claim is "it's a BST because 4>3 and 4<7":
5
/ \
3 7
/
4
Where's the error?
4 sits in 5's right subtree, so it must be , but . It obeys its immediate parent 7 yet violates the ancestor 5 — invalid.
"Swapping the two recursive calls in inorder (do right before left) still prints sorted." — true?
False. R,N,L prints the larger family first, giving decreasing order. The exact L,N,R order is what forces increasing output.
"I appended the node before recursing left." — what output do you get?
You get Node–Left–Right (preorder), which prints a node before its smaller descendants — not sorted. The append must sit between the left and right recursions.
Why questions
Why does inorder produce sorted order specifically, and not preorder or postorder?
Because at each node inorder prints the entire smaller-left family, then the node, then the larger-right family. Pre/postorder place the node before or after both subtrees, breaking the smaller-then-node-then-larger ordering.
Why is structural induction the natural proof technique here?
A BST is defined recursively (subtrees are themselves BSTs), so we prove the base case (empty/single node) then assume it for smaller subtrees and stitch the sorted pieces around the root.
Why is "last of the left list root, and root first of the right list" the crucial fact in the proof?
Concatenating two sorted lists stays sorted only if the last of the first is the first of the second. Those two boundary inequalities guarantee the joins don't break sortedness.
Why does the explicit stack in iterative inorder exist at all?
It remembers the postponed "visit this node, then go right" work for every ancestor while we dive down the left spine — exactly what the recursion's call stack would hold.
Why does finding the kth smallest not need to finish the whole traversal?
Inorder emits keys in increasing order, so the kth emitted value is the kth smallest — you can stop the moment the counter hits k.
Why do self-balancing trees matter for traversal cost even though inorder is either way?
They bound height to , which keeps the traversal's stack/recursion space small; a skewed tree pushes space.
Edge cases
What does inorder return for a completely left-skewed tree (each node has only a left child)?
The keys in increasing order, same as any BST — the tree is just a sorted linked list, and inorder still walks it time, space.
What is the inorder output of a tree with exactly one node?
A single-element list, which is trivially sorted — this is the base case of the correctness proof.
If duplicate keys are allowed and stored in the right subtree, does inorder still sort?
Yes, it returns a non-decreasing (sorted with repeats) list, but you must validate with
prev <= cur, not prev < cur, to accept the equal neighbours.What happens to the sortedness guarantee if a single subtree secretly violates the BST rule?
It breaks locally: the offending key appears out of order in the output, which is precisely how an inorder-based validity check detects the violation.
For a tree that is a single right-skewed chain of increasing keys, how much stack does iterative inorder use?
Only effective depth at a time — you push a node, immediately pop and print, then move right, so the stack never holds more than one node despite height .
Connections
- Binary Search Tree — the invariant these traps probe.
- Tree Traversals — why pre/postorder do not sort.
- Validate BST — the direct payoff of the sorted-inorder fact.
- Binary Search — same left-smaller/right-larger logic on arrays.
- Structural Induction — the proof several "why" items reference.
- AVL & Red-Black Trees — keep height small for cheap traversal.
- Kth Smallest Element in BST — early-stopping application.