A tree has no single obvious reading order the way a line of text does -- there's no "top-left corner to start from." Visiting every vertex exactly once still needs a rule, and three particular rules turn out to matter enough to have their own names, each one a different answer to "when, relative to its children, does a vertex itself get visited?"
Picture a company org chart as the tree, with the CEO at the root. Preorder announces each manager before touring their team: CEO first, then everyone under them. Postorder is the reverse -- tour an entire team first, and only name the manager once every person under them has already been introduced, working all the way up to the CEO last. Inorder only makes sense when a manager has exactly a "left" report and a "right" report to sandwich themselves between, which is why it's a binary-tree-only rule. Same tree, same three people to introduce at every level -- only the order the names get called out changes.
Tree traversal is the problem of visiting every vertex of a tree exactly once, in an order fixed by one of three named rules, each defined recursively at every vertex v with children:
- Preorder: visit v itself, then traverse each of v's subtrees, left to right.
- Postorder: traverse each of v's subtrees, left to right, then visit v itself.
- Inorder (binary trees only, since it needs exactly a "left" and a "right" subtree to place v between): traverse v's left subtree, then visit v, then traverse v's right subtree.
All three agree on two things: every vertex is visited exactly once, and a subtree is always fully finished before the traversal moves past it to whatever comes next. They differ only in when v itself gets recorded relative to its own subtrees -- first, last, or (for a binary tree) in the middle.
Quick review
Practice from earlier coursework, pulled in for this topic.
From Discrete Mathematics I — Logic, Proof, and Structure
The same tree (root 5, left child 3, right child 9) is traversed inorder. What is the result?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
That order is preorder, not inorder.
That reverses the correct inorder result.
That order is postorder, not inorder.
Why
Inorder visits the left subtree (3), then the root (5), then the right subtree (9).
From Discrete Mathematics I — Logic, Proof, and Structure
Why is inorder traversal typically defined only for binary trees, not general rooted trees?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Leaf existence has nothing to do with why inorder needs exactly two subtrees.
General trees can be traversed just fine, with preorder and postorder.
With three or more children, or exactly one, there is no natural place to put the vertex in the middle.
Why
Inorder specifically visits left subtree, then vertex, then right subtree -- a rule that only makes sense with exactly two subtrees to place the vertex between.
From Discrete Mathematics I — Logic, Proof, and Structure
In preorder traversal, when is a vertex visited relative to its subtrees?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
That describes postorder, not preorder.
That describes inorder, and only applies cleanly to binary trees.
Traversal order is fixed by definition, not random.
Why
Preorder visits the vertex itself first, then recursively traverses each subtree.
Click the vertices in postorder
Click each vertex, in the order postorder traversal visits it -- every vertex only after both of its subtrees are fully visited.
Loading interactive…
Worked example
Tracing a preorder traversal
-
1
List the preorder traversal of the tree rooted at M, whose left subtree is rooted at F (children B, H) and right subtree is rooted at T (children Q, X).
-
2
Preorder visits the root first: write down M. Then traverse the left subtree in preorder: visit F first, then its children B and H, in that order.
-
3
Then traverse the right subtree in preorder the same way: visit T first, then its children Q and X.
-
4\boxed{M, F, B, H, T, Q, X}
Loading interactive…
Worked example
Tracing an inorder traversal of the same tree
-
1
List the inorder traversal of the same tree.
-
2
Inorder visits the left subtree first. Within that subtree rooted at F: its left child B, then F itself, then its right child H.
-
3
Then visit the root M, then repeat the pattern on the right subtree rooted at T: left child Q, then T, then right child X.
-
4\boxed{B, F, H, M, Q, T, X}
Loading interactive…
Worked example
Recognizing which order produced a given list
-
1
A traversal of the same tree (root M, left subtree F with children B, H; right subtree T with children Q, X) produced the list B, H, F, Q, X, T, M. Which traversal order was used?
-
2
Check where the root, M, lands: it's last on this list, which already rules out preorder (root first) and inorder (root sits between the two subtrees, not at the very end).
-
3
Check postorder directly: it should list the entire left subtree, then the entire right subtree, then the root -- B, H, F (left), Q, X, T (right), then M.
-
4\boxed{\text{postorder}}
Who uses this
File systems and directory tools
A file-system utility that computes a folder's total size has to visit every file inside every subfolder before it can report the parent folder's own total -- that's postorder, a folder's number depending on its children being finished first. A utility that just prints a directory listing top-down, folder name before its contents, is running preorder instead. Same three rules from this section, doing real, everyday work any time software has to walk a folder tree.
Check your understanding (counts toward your progress)
Which traversal order only applies cleanly to binary trees, and not to a general tree with more than two children per vertex?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Preorder works for any number of children -- visit the vertex, then each subtree in turn.
Postorder also generalizes fine -- visit each subtree in turn, then the vertex.
One of the three specifically needs a left/right split to even be defined.
Why
Inorder is defined as left-subtree, then vertex, then right-subtree -- a definition that only makes sense when there are exactly two subtrees to place the vertex between.
A tree has 9 vertices. How many entries does its preorder traversal list contain?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Every traversal order visits each vertex exactly once, so the list always has exactly as many entries as the tree has vertices, regardless of which order is used.
Correct answer
Also accepted:
Why
Recall whether any traversal order ever skips a vertex or visits one more than once.
A tree consists of a single vertex, with no children at all. What do its preorder, inorder, and postorder traversals look like?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
With nothing to place before, after, or between, all three definitions collapse to the same trivial case here, not just two of them.
The single vertex is still visited -- the list has exactly one entry, not zero.
A one-vertex tree traverses just fine -- there's simply nothing else to visit.
Why
With no subtrees at all, 'before its subtrees,' 'after its subtrees,' and 'between its subtrees' are all vacuously true at once -- every order reduces to just visiting the single vertex.
Ask what 'before its subtrees,' 'after its subtrees,' and 'between its subtrees' even mean when there are no subtrees at all.
Decide whether that makes the three orders diverge, or collapse to the exact same thing.
In a preorder traversal, when is a vertex v itself recorded, relative to its subtrees?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
That describes postorder, not preorder.
That describes inorder, and only makes sense for a binary tree with a distinct left/right split.
Why
Preorder records the root of each subtree first, before recursing into the subtree's own children.
Practice: Reading and predicting traversal order (4 problems · doesn’t affect your progress)
In postorder, when is the root of the whole tree recorded?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Postorder finishes every subtree before recording the vertex itself, so the root -- whose subtrees all finish last -- is recorded last of all.
Last
Which traversal order needs a tree to have a clear left subtree and right subtree to even be defined?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Inorder places the vertex specifically between its left and right subtree, which only makes sense for a binary tree.
Inorder
A tree has 12 vertices. How many entries does its postorder traversal list?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Every traversal order visits each vertex exactly once, regardless of the order chosen.
Correct answer
Also accepted:
Why
Recall whether any traversal order ever skips or repeats a vertex.
A traversal list has the root recorded first, immediately followed by an entire subtree, then the next subtree, and so on. Which order is this?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Root first, then each subtree fully traversed in turn, is exactly preorder's definition.
Compare this pattern against where each of the three orders places the root relative to the subtrees.
Check specifically which order visits the root before recursing into any subtree at all.
Preorder