In-Order vs Pre-Order Traversal
Use in-order on a binary search tree, where it emits the values in sorted order. Use pre-order when you need the node before its children, which is what copying, serialising and printing a structure all require.
The three depth-first orders differ in one thing: when the node itself is handled relative to its two subtrees. That single choice decides what each order is good for. In-order gives you sorted values on a BST. Pre-order gives you a parent before anything that depends on it. Post-order gives you children before their parent.
Side by side
| Dimension | In-order | Pre-order |
|---|---|---|
| Order | Left, node, right | Node, left, right |
| On a BST | Sorted ascending | No useful ordering |
| Rebuilding the tree | Not enough on its own | Enough with nulls recorded, or paired with in-order |
| First value emitted | The smallest, the leftmost leaf | The root |
| Classic uses | Kth smallest, validate a BST, sorted export | Copy a tree, serialise, print a directory listing |
| Iterative form | Push lefts, pop, go right | Push root, pop, push right then left |
When to pick each
In-order
- Kth smallest or kth largest in a BST, where you stop after k visits rather than traversing everything.
- Validating a BST, since the in-order sequence of a valid tree is strictly increasing.
- Anything that wants the values in order without sorting them.
Pre-order
- Serialising a tree, because the reader can rebuild it in the same order the writer emitted it.
- Copying or cloning, where a parent must exist before its children can be attached.
- Rendering a hierarchy, such as a file tree, where the folder is printed above its contents.
Assuming a pre-order sequence identifies a tree. Several different trees produce the same pre-order, so serialising without recording the nulls loses the shape and the reader rebuilds something else. Pre-order paired with in-order does pin the tree down, which is why the reconstruction question asks for both, and even that fails if the values contain duplicates.
Questions people ask
Which order should I default to on a tree problem?
Ask what each node needs. If it needs an answer from its children, that is post-order. If it needs something handed down from its parent, such as a valid range or an accumulated path, that is pre-order. If the tree is a BST and the question involves ordering or rank, that is in-order. The order is a consequence of the data flow, not a style choice.
Does in-order mean anything on a tree that is not a BST?
Not usually. Without the ordering invariant the sequence has no meaning beyond the shape of the tree, so problems on general binary trees reach for pre-order, post-order or level-order instead. Expression trees are the exception: in-order on one of those reproduces the infix expression.
Can I do in-order without a stack?
Yes, with Morris traversal, which threads each node's spare right pointer back to its in-order successor and so walks the tree in O(1) space. The catch is that it mutates the tree while running. The structure is restored by the end, but a concurrent reader would see something broken, so it is unsafe on anything shared.