Which traversal of a binary search tree visits the keys in sorted order, and how does that traversal work?

technical-conceptual · Junior level · software-engineering

What the interviewer is really asking

Tests whether the candidate knows the in-order traversal, why it yields sorted output on a BST, and can distinguish it from pre-order and post-order.

What to say

• Name it: an in-order traversal (left subtree, then node, then right subtree) visits a BST's keys in ascending sorted order.
• Explain why: the BST invariant guarantees the left subtree holds all smaller keys and the right holds all larger ones, so visiting left-then-node-then-right at every node produces a globally ascending sequence.
• Contrast the siblings: pre-order (node, left, right) is used to copy/serialize a tree, and post-order (left, right, node) to delete or evaluate it — only in-order gives sorted output on a BST. All three are O(n).

What to avoid

• Say pre-order or post-order produces sorted output — only in-order does on a BST.
• Recite the three orders without being able to explain why in-order specifically yields sorted keys.
• Claim it needs the tree to be balanced; in-order yields sorted keys on any valid BST regardless of shape.

Example answers

Strong: In-order traversal gives sorted output: you recurse into the left subtree, visit the current node, then recurse into the right subtree. It works because of the BST invariant — at every node the left subtree is all smaller and the right is all larger, so left-node-right at each step strings the keys together in ascending order. It's O(n) since you touch each node once.

Weak: I think it's pre-order — you visit the root first so you get them in order.