Quiz Entry - updated: 2026.09.29
What is a tree traversal, and which kinds exist?
A traversal visits every node of a tree exactly once, in a systematic order. The four standard orders are preorder, postorder, breadth-first and, for binary trees, inorder.
"Visit" stands for whatever the application needs to do with a node: print it, add up its size, evaluate it. The traversal only fixes the order in which nodes get visited, and each order suits different tasks:
| Traversal | Order | Typical use |
|---|---|---|
| Preorder | node, then its children's subtrees | printing a structured document top-down |
| Postorder | children's subtrees, then the node | computing folder sizes, evaluating expressions |
| Breadth-first | level by level, top to bottom | shortest distance from the root, level-wise processing |
| Inorder (binary only) | left subtree, node, right subtree | printing expressions, sorted output of a search tree |
Every one of them visits each node once, so each runs in $O(n)$ for a tree of $n$ nodes.
The first three work on any tree. Inorder needs a binary tree, because "between the left and right subtree" only makes sense when there are exactly two sides.
Go deeper:
Tree traversal — all four orders with pseudo-code, recursive and iterative.