Which traversal method lists the nodes of a binary search tree in sorted order?

In a Binary Search Tree (BST), every node satisfies the BST invariant: for any node, all keys in its left subtree are smaller than the node's key, and all keys in its right subtree are larger. Inorder traversal recursively visits a node's left subtree, then the node itself, then its right subtree. Because this ordering always processes smaller keys (left) before a node and larger keys (right) after it, applying inorder traversal to any BST outputs its keys in non-decreasing (sorted) order.

Consider the BST formed by inserting the keys 5, 3, 8, 1, 4, 7, 9 in that order: the root is 5, with left child 3 and right child 8; node 3 has left child 1 and right child 4; node 8 has left child 7 and right child 9. Tracing inorder traversal (left, root, right) on this tree, step by step:

1. Start at the root (5) and recurse into its left subtree first (node 3).

2. At node 3, recurse into its left subtree first (node 1).

3. Node 1 has no left child, so visit it now — output so far: 1. It has no right child, so control returns to node 3.

4. Visit node 3 — output so far: 1, 3. Then recurse into its right subtree (node 4).

5. Node 4 has no children, so visit it — output so far: 1, 3, 4. Control returns up to the root.

6. Visit the root, node 5 — output so far: 1, 3, 4, 5. Then recurse into its right subtree (node 8).

7. At node 8, recurse into its left subtree first (node 7). Node 7 has no children, so visit it — output so far: 1, 3, 4, 5, 7.

8. Visit node 8 — output so far: 1, 3, 4, 5, 7, 8. Then recurse into its right subtree (node 9). Node 9 has no children, so visit it — final output: 1, 3, 4, 5, 7, 8, 9.

The final sequence 1, 3, 4, 5, 7, 8, 9 is fully ascending, confirming the concept. Applying the other traversals to the same tree does not reproduce this order: preorder (root, then left, then right) gives 5, 3, 1, 4, 8, 7, 9; postorder (left, then right, then root) gives 1, 4, 3, 7, 9, 8, 5; and level order (breadth-first by depth) gives 5, 3, 8, 1, 4, 7, 9 — none of these is sorted. Only inorder traversal exploits the BST invariant to guarantee ascending output, and it does so in O(n) time using O(h) auxiliary recursion-stack space, where h is the height of the tree.