In-order traversal visits the left subtree, then the node, then the right subtree, and the BST invariant puts those three parts in ascending order. Everything in a node's left subtree is smaller than the node, and everything in its right subtree is larger. So the traversal emits all smaller values before the node and all larger values after it. The same holds at every level, so the whole sequence comes out ascending.
inorder(node.left);
visit(node.val);
inorder(node.right);
// prints values low to high
This gives you a free sorted listing in O(n) without any extra sorting step. It also means you can spot a broken tree cheaply. If an in-order pass ever emits a value smaller than the previous one, some node violates the invariant.
Rewriting in plainer words…
This answer doesn't lend itself to a diagram - it reads best . No credits were charged.
How would you get the kth smallest value, and when can you stop the walk early?Count visits during the in-order walk and stop at k, which costs O(h + k). For repeated queries, store subtree sizes in each node.
How do duplicate keys change the in-order output and your validity check?If equal keys always go to the same side, the output is non-decreasing. The check must then allow equal neighbours, so choose < or <= to match that rule.
What you can say
In-order visits the left subtree, then the node, then the right subtree, and the BST invariant says that is exactly smallest to largest.
Everything in a node's left subtree is smaller than the node, and everything in its right subtree is larger.
So at any node, the walk emits all the smaller values first, then the node, then all the larger ones.
The same argument holds at every level of the recursion, so the whole sequence comes out ascending, and you get a sorted listing in O(n) with no sorting step.
The guarantee only holds if the invariant does, and that makes it a cheap check. If the walk ever emits a value smaller than the one before it, some node breaks the rule.
Weak answers to avoid
Answers 'because it's a BST' and stopsThat restates the question. Line up left, node, right against smaller, node, larger, then say why the same thing holds at every level.
Treats the invariant as parent-versus-child onlyComparing a node with its direct children doesn't prove all left values come first. The rule covers whole subtrees, and the argument depends on that.
Mixes up in-order with pre-order or level-orderPre-order emits the node before its subtrees and level-order goes row by row. Only left-node-right matches the BST's ordering.
Interview lens
Likely follow-ups, what you can say, and the weak answers to avoid.
