In preorder, inorder and postorder traversal of a binary tree, what actually changes between them?
answer
- Three actions at every node
- Left before right stays fixed
- Only one of the three moves
- Pre, in, post name a position
- Position of the node's own visit
basics
~20 sAll three walk the left subtree before the right; only the position of the node's own visit moves — before both subtree walks (preorder), between them (inorder), or after both (postorder). All three are depth-first and all cost O(n).
solid answer
~50 sThe three orders share the same route through the tree and differ in one thing: when the current node is handled relative to its two recursive descents. Preorder handles the node, then the left subtree, then the right; inorder goes left, node, right; postorder goes left, right, node. The child order itself is fixed — left before right in all three — so a candidate who says they differ in "which child comes first" has the wrong axis. All three are depth-first: each dives to a leaf before backing up, and none of them produces output tier by tier the way a queue-driven level-order walk does. Each costs O(n) time because every node is handled exactly once and every link is followed twice — down and back up — and each uses space proportional to the tree's height for the pending descents.
go deeper
Be ready to state all three orders in one breath and produce their sequences for a three- or five-node tree on the spot. Remember the moving part is the node's own visit, not the child order.
Explain that all three are one depth-first route with the emit point moved, that level-order is a genuinely different route, and why the linear cost is identical across all of them.
Show that you pick an order from the task's data dependency rather than habit, and that you can say what each order gives you when reviewing someone else's tree-walking code.
Own the vocabulary question: when a codebase has five hand-rolled walks over the same structure, decide whether one shared traversal with a visit callback is worth the indirection, and how you would name the orders so reviewers stop guessing.
## The one thing that moves A traversal of a binary tree is a rule for ordering three actions at every node: 1. handle the node itself ("visit": print it, copy it, sum it, free it), 2. walk the left subtree, 3. walk the right subtree. The two subtree walks always happen, and by convention they always happen **left before right**. So the only degree of freedom is *where the visit lands among them*, and that gives exactly three orders: | Order | Sequence at every node | Node visited… | |---|---|---| | preorder | node, left, right | before both descents | | inorder | left, node, right | between the descents | | postorder | left, right, node | after both descents | The names say it outright: *pre*, *in*, *post* describe the position of the node's visit relative to the subtree walks. That is the whole distinction, and it is the answer an interviewer is listening for. ## A trace Take a three-node tree: root `R`, left child `L`, right child `X`, both children leaves. - preorder: `R, L, X` - inorder: `L, R, X` - postorder: `L, X, R` Every sequence contains the same nodes; the root slides from front to middle to back. Extend to a deeper tree and the same rule applies recursively at every node, not just the root — a frequent junior slip is to apply the rule only at the top and then walk the subtrees in some other order. ## All three are depth-first All three descend as far as they can before backing up, so all three are depth-first orders; they are three *readouts* of one depth-first walk. The walk itself — the physical route through the tree — is identical in all three cases. If you instrument the code, the sequence of nodes *entered* is the same; only the moment at which you emit the node differs. This is why converting between them is a matter of moving one line, not restructuring the traversal. The fourth traversal, level-order, is genuinely a different route: it visits every node at depth 0, then every node at depth 1, and so on, which no reordering of the three recursive lines can produce. It needs a first-in-first-out queue rather than the last-in-first-out behaviour that recursion gives you. Calling preorder "breadth-first because it starts at the root" is a classic confusion — every traversal starts at the root. ## Cost All four are O(n) time on an n-node tree. The reasoning is simple and worth being able to say out loud: each node is entered once and visited once, each of the n−1 links is followed once downward and once on the way back, and the per-node work is constant, so the total is linear. The order in which nodes come out does not change how many of them there are. Space differs by mechanism, not by order: the three depth-first orders keep one pending frame per ancestor of the current node, so they use space proportional to the tree's **height** — modest for a bushy tree, but proportional to n for a long thin one. A queue-driven level-order walk instead holds a level's worth of nodes. ## Mirror images Nothing forces left-before-right; it is a convention. Swap the two descents and you get three mirrored orders (node-right-left, right-node-left, right-left-node). That is worth knowing because one useful identity falls out of it: reversing the *mirrored* preorder sequence (node, right, left) yields postorder. Reversing plain left-first preorder does **not** — a trap that shows up in interviews. ## What people get wrong - "They differ in which child is visited first." No — left precedes right in all three; the node's own visit is what moves. - "Preorder is depth-first, postorder is bottom-up, so they are different algorithms." They are the same walk emitting at different moments. - "Inorder is the natural one and the others are variants." All three are equally natural; which one is *correct* depends entirely on the task. - "Preorder always outputs the root first, so it's the fastest." Output position has nothing to do with cost; all are linear. Being able to state the definitions crisply is the entry ticket. The follow-up that actually separates candidates is *which order a given task requires* — copying, releasing, aggregating and displaying a tree each pin down a different one.
- Why is every one of these traversals O(n) regardless of the tree's shape?Each node is entered and visited exactly once and each link is followed twice — once down, once back — with constant work per node, so the total is linear in n. Shape changes the recursion depth and therefore the space, not the count of visits. A long thin tree costs the same time as a perfectly bushy one of the same size.
- Which of the three can you get by reversing another one, and what is the catch?Postorder is the reverse of the mirrored preorder — the variant that visits node, then right subtree, then left. Reversing ordinary left-first preorder does not give postorder; it gives node-right-left read backwards, which is a different sequence. State the mirror step explicitly or the identity is simply wrong.
- Is level-order just a fourth reordering of the same three lines?No. The three depth-first orders are three emit points inside one identical route through the tree. Level-order is a different route — all of depth 0, then all of depth 1 — and no placement of the visit inside a recursive left/right descent produces it. It needs a first-in-first-out queue instead of recursion's last-in-first-out behaviour.
Narrating a tour of a building with two wings: you can announce the floor before walking both wings, between them, or after both. The walking route never changes — only when you speak.
saying these in an interview costs you the question
- Says the three orders differ in which child is walked first
- Calls preorder breadth-first because it starts at the root
- Applies the ordering rule only at the root, not recursively
- Claims one of the three is asymptotically cheaper than the others
- Says postorder is plain preorder reversed, with no mirror step