Three Ways to Visit the Nodes
A rooted tree gives a hierarchy: each node has a parent, except the root, and may have children. In an ordered binary tree, each node has at most two children, distinguished as its left child and its right child. The order matters. Preorder, inorder, and postorder use these positions to specify when to visit a node relative to its two subtrees.
All trees in this tutorial are finite. A node may have no children, only a left child, only a right child, or both children. In particular, a binary tree need not be full. We treat a missing child as an empty subtree, whose traversal sequence contains no nodes. For the empty tree itself, all three traversal sequences are empty.
Write \(P(T)\), \(I(T)\), and \(Q(T)\) for the preorder, inorder, and postorder sequences of a tree \(T\). Concatenation means writing one sequence immediately after another. The recursive rules are
These rules apply even when a subtree is empty: its sequence contributes nothing. They also describe a direct procedure. At each node, apply the same rule to the left subtree and then the right subtree, placing the node itself at the position specified by the traversal. The rule is recursive because each subtree is itself an ordered binary tree.
Worked Traversals
Worked Example: A Full Binary Tree
Let \(G=(V,E)\) be the tree with \(V=\{1,2,3,4,5,6,7\}\) and \(E=\{12,13,24,25,36,37\}\). Take \(1\) as the root. Its left and right children are \(2\) and \(3\); the children of \(2\) are \(4\) on the left and \(5\) on the right; the children of \(3\) are \(6\) on the left and \(7\) on the right. Nodes \(4,5,6,7\) are leaves.
Calculate the sequences from the leaves upward. A leaf contributes itself in all three orders. At node \(2\), the left subtree contributes \(4\) and the right subtree contributes \(5\). At node \(3\), they contribute \(6\) and \(7\). The subtree calculations are:
| Subtree root | Preorder | Inorder | Postorder |
|---|---|---|---|
| 4 | 4 | 4 | 4 |
| 5 | 5 | 5 | 5 |
| 2, with children 4 and 5 | 2, 4, 5 | 4, 2, 5 | 4, 5, 2 |
| 6 | 6 | 6 | 6 |
| 7 | 7 | 7 | 7 |
| 3, with children 6 and 7 | 3, 6, 7 | 6, 3, 7 | 6, 7, 3 |
Now combine the two subtree results at root \(1\). Preorder puts \(1\) first, so it is \(1,2,4,5,3,6,7\). Inorder puts \(1\) between the two subtree sequences, giving \(4,2,5,1,6,3,7\). Postorder puts \(1\) last, giving \(4,5,2,6,7,3,1\).
Check: Each sequence contains all seven labels once. In preorder the root \(1\) is first; in inorder it separates the left-subtree labels \(4,2,5\) from the right-subtree labels \(6,3,7\); in postorder it is last. The edge set has six edges for seven vertices, consistent with this connected tree.
Worked Example: Missing Left and Right Children
Let \(G=(V,E)\) have \(V=\{a,b,c,d,e,f\}\) and \(E=\{ab,ac,bd,df,ce\}\), rooted at \(a\). At \(a\), the left child is \(b\) and the right child is \(c\). Node \(b\) has no left child and has right child \(d\); node \(d\) has left child \(f\) and no right child. Node \(c\) has left child \(e\) and no right child. Nodes \(e\) and \(f\) are leaves.
First calculate the small subtrees. At \(d\), the left subtree is the leaf \(f\), so \(P(d)=d,f\), \(I(d)=f,d\), and \(Q(d)=f,d\). At \(b\), the left subtree is empty and the right subtree is rooted at \(d\), so \(P(b)=b,d,f\), \(I(b)=b,f,d\), and \(Q(b)=f,d,b\). At \(c\), the left subtree is the leaf \(e\) and the right subtree is empty, so \(P(c)=c,e\), \(I(c)=e,c\), and \(Q(c)=e,c\).
At the root, combine the left-subtree results from \(b\) and the right-subtree results from \(c\). Thus preorder is \(a,b,d,f,c,e\); inorder is \(b,f,d,a,e,c\); and postorder is \(f,d,b,e,c,a\).
Check: The three outputs each contain \(a,b,c,d,e,f\) exactly once. The missing-child positions are respected: in inorder, for example, \(b\) appears before its only child-subtree sequence \(f,d\), because \(b\) has no left child and its child \(d\) is on the right. The five listed edges connect six vertices without a cycle, as required for a tree.
Worked Example: A Single Child on Each Side of the Root
Let \(G=(V,E)\) have \(V=\{r,x,y,z,w\}\) and \(E=\{rx,ry,xz,yw\}\), rooted at \(r\). The left child of \(r\) is \(x\), and its right child is \(y\). Node \(x\) has left child \(z\) and no right child; node \(y\) has no left child and right child \(w\). The nodes \(z,w\) are leaves.
At \(x\), preorder is \(x,z\), inorder is \(z,x\), and postorder is \(z,x\). At \(y\), preorder is \(y,w\), inorder is \(y,w\), and postorder is \(w,y\). Combining at \(r\), preorder is \(r,x,z,y,w\). Inorder is \(z,x,r,y,w\). Postorder is \(z,x,w,y,r\).
Check: Every output contains the five vertices exactly once. In the preorder sequence, \(r\) precedes both subtrees; in postorder it follows both. In the inorder sequence, the entire left subtree \(z,x\) precedes \(r\), and the entire right subtree \(y,w\) follows it. These checks match the root’s specified left and right child positions.
Why the Recursive Rules Work
Proof. We use induction on the number \(n\) of nodes. If \(n=0\), the tree is empty, and each sequence is empty, so the claim holds. Now suppose \(n\ge 1\), and assume the claim holds for every ordered binary tree with fewer than \(n\) nodes. Let \(r\) be the root, with left subtree \(L\) and right subtree \(R\). Each nonempty one of \(L\) and \(R\) has fewer than \(n\) nodes, so the induction hypothesis applies to it; an empty subtree contributes no nodes.
The vertex sets of \(L\), \(R\), and \(\{r\}\) are disjoint and together contain all nodes of the tree. By induction, each nonempty subtree’s traversal lists each of its nodes exactly once. Each defining rule concatenates the two subtree sequences and the single occurrence of \(r\), so the resulting sequence lists every node exactly once. The positions of these three pieces in the rules are precisely the stated orders: root-left-right for preorder, left-root-right for inorder, and left-right-root for postorder. This proves both the no-repetition and the order claims for all three traversals. \(\square\)
The proof also explains why the procedure terminates: every recursive call is made on a subtree with fewer nodes than the original tree. Repeatedly taking smaller subtrees must eventually reach an empty tree or a leaf. For a leaf, both child subtrees are empty, so the rule returns that leaf alone.
Reading the Output and Avoiding Errors
A traversal sequence records node labels in visit order; it does not change the tree’s edges or child positions. In particular, an inorder sequence is not automatically a sorted list. It places a node between its left and right subtree sequences, but it gives a sorted list only when the tree has an additional ordering property, which is not assumed here.
Left and right positions also cannot be discarded. For instance, let \(V=\{r,a,b\}\) and \(E=\{ra,rb\}\). If \(a\) is the left child and \(b\) the right child, the preorder is \(r,a,b\) and the inorder is \(a,r,b\). If the child positions are swapped, while keeping the same vertices and edges, preorder becomes \(r,b,a\) and inorder becomes \(b,r,a\). The unrooted edge set alone does not specify these traversal outputs; the root and ordered child positions are part of the input.
Common mistake. Suppose node \(b\) has no left child and has right child \(d\), whose left child is \(f\). A wrong inorder calculation is \(f,d,b\), obtained by putting \(b\) after its child. That order is postorder for this subtree, not inorder. In inorder, a node is placed after its left subtree and before its right subtree. Since \(b\)'s left subtree is empty, the correction is \(b,f,d\). Applying the same rule at \(d\) gives \(f,d\), and then applying it at \(b\) gives \(b,f,d\).
When checking a computed traversal, verify that its length equals the number of nodes and that each label occurs once. Then check the root position: first in preorder, between the subtree sequences in inorder, and last in postorder. Finally, confirm that the subtree sequences appear in left-then-right order. These checks catch omissions, repetitions, and accidental reversals.
Check Your Understanding
For each question, use the specified root and left-right child positions. Treat any missing child as an empty subtree.
- For \(V=\{1,2,3,4\}\), \(E=\{12,13,24\}\), rooted at \(1\) with left child \(2\), right child \(3\), and left child \(4\) of \(2\), find all three traversals.
- Explain why a node with only a right child appears before that child in inorder.
- For a nonempty ordered binary tree, where must its root appear in preorder, inorder, and postorder?
- Prove that the traversal of an empty tree contains no labels and that the rule for a one-node tree returns its single label in all three orders.
- Give an example of a rooted tree whose preorder and postorder sequences differ, and identify the root in each sequence.