1
The name says when the root is visited
Pre: before the subtrees. In: between them. Post: after both. Everything else is the same recursion.
Lesson · Graphs and Trees · Trees
Rooted Trees and Traversals
A rooted tree is visited in one of three canonical orders, distinguished by when the root is handled. Each is a structural induction, and each is the right one for a different job.
PREORDER root, then left subtree, then right — copying, prefix notation
INORDER left, root, right — sorted order in a BST
POSTORDER left, right, then root — evaluation, deletion
all three are structural induction (“Structural Induction” in Induction and Recursion)
Where the root goes
Core ideas
What this lesson establishes
Three orders, differing only in when the root is visited, and each is right for a different task.
2
Each is a structural induction
The recursive definition of a binary tree from “Recursive Definitions” in Induction and Recursion gives the recursion directly.
3
Inorder on a search tree gives sorted order
That is the defining property of a binary search tree, and it is why inorder matters.
The material
Traversals
The three orders, their uses, and the expression-tree example.
PREORDER(v): visit v; PREORDER(left); PREORDER(right)
INORDER(v): INORDER(left); visit v; INORDER(right)
POSTORDER(v): POSTORDER(left); POSTORDER(right); visit v
Each is the recursive definition of a binary tree with the visit inserted at a different point, so each is a structural induction in the sense of “Structural Induction” in Induction and Recursion. Every node is visited exactly once and the cost is Θ(n).
Expression trees
An arithmetic expression is a binary tree: operators are internal nodes and operands are leaves. The three traversals produce the three standard notations.
+
/ \
* 5
/ \
3 4
PREORDER + * 3 4 5 prefix (Polish)
INORDER 3 * 4 + 5 infix — needs parentheses in general
POSTORDER 3 4 * 5 + postfix (reverse Polish)
Postfix is what stack-based evaluators consume: read left to right, push operands, and on an operator pop two and push the result. No parentheses and no precedence rules are needed, because the tree structure is already encoded in the order.
Infix is the notation people read and the only one of the three that is ambiguous without parentheses or precedence conventions — which is the whole reason “Logical Connectives” in Logic and Proof had to state a precedence order.
Binary search trees
Definition · Binary search tree
A binary tree in which every node's key exceeds all keys in its left subtree and is less than all keys in its right subtree.
Theorem · Inorder gives sorted order
An inorder traversal of a binary search tree visits the keys in increasing order.
By structural induction. The empty tree is vacuous.
For a node with subtrees L and R: by the hypothesis the traversal visits L's keys in increasing order, all less than the root; then the root; then R's keys in increasing order, all greater. The concatenation is increasing.
□
Searching a balanced binary search tree costs Θ(log n), one comparison per level, which is the binary search of “Searching and Sorting”, in Algorithms and Complexity, reorganised as a data structure. If the tree is unbalanced — a path — it degenerates to Θ(n), which is why balancing schemes exist.
Other traversals
Level order visits by depth and is exactly breadth-first search from the root, using a queue rather than recursion. It is the traversal that prints a tree row by row.
For non-binary rooted trees, preorder and postorder generalise directly — visit the children in order — while inorder does not, since there is no single place for the root among three or more children.
Interactive
Graph workbench
Your graph, the course's algorithms
Method
Traversing a tree
Pick the order from the task.
1
Preorder to copy or serialise
The root is emitted before its subtrees, so the structure can be rebuilt as it is read.
2
Inorder for a search tree
It produces the keys in sorted order, which is what the structure exists for.
3
Postorder to evaluate or delete
Children are finished before the parent, which is what evaluation and safe deallocation both require.
4
Level order to see the shape
Breadth-first from the root. It is the traversal that shows depth and balance.
Traversals
Score 0 / 0Choose the answer you can justify.
All three orders on one tree
A binary search tree containing 2, 3, 5, 6, 7, 8.
6
/ \
3 8
/ \ /
2 5 7
PREORDER 6 3 2 5 8 7 root first — reconstructible
INORDER 2 3 5 6 7 8 SORTED, as a BST must be
POSTORDER 2 5 3 7 8 6 children before parents
LEVEL 6 3 8 2 5 7 by depth
Only inorder is sorted, and that is the property that makes the
structure a search tree rather than an arbitrary binary tree.
Preorder alone determines the tree when it is a binary search tree, because the ordering constraint says where each subsequent key belongs. For a general binary tree it does not: preorder plus inorder is needed to reconstruct the shape.
Common mistakes
1
Expecting preorder to be sorted on a search treeOnly inorder is. Preorder visits the root first, which is by definition not the smallest key.
2
Trying to define inorder for a general rooted treeWith three or more children there is no single place for the root. Pre- and postorder generalise; inorder does not.
3
Assuming one traversal determines the treeFor a general binary tree, preorder plus inorder is needed. One sequence is consistent with many shapes.
Check your understanding
✓
Finish when you can produce all three orders from a drawing.
Build a binary search tree by inserting 5, 3, 8, 1, 4, 7, 9 in that order, then write all three traversals. The inorder must come out sorted, which is a check on the insertion: preorder 5 3 1 4 8 7 9, inorder 1 3 4 5 7 8 9, postorder 1 4 3 7 9 8 5.
Note: Postorder is why reverse Polish notation needs no parentheses: the traversal order already encodes the tree structure, so precedence never has to be inferred. Calculators and stack machines consume it directly.