In-order traversal visits the left subtree, then the node, then the right subtree, recursively. Pair that order with the BST invariant and sorted output falls out naturally.
The invariant guarantees everything left of a node is smaller and everything right is larger. So by fully processing the left subtree before touching the node, you emit all smaller values first. Then the node, then all larger values from the right subtree. Apply that reasoning at every level and 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, the invariant is violated somewhere.
This answer doesn't lend itself to a diagram - it reads best . No credits were charged.
Why there's no diagram: “”
The interactive diagram is below the answer - jump to diagram ↓ · Below it, the related concept . Jump to it ↓
The diagram below the answer is the concept . Jump to it ↓