Three orders to visit every node
Preorder, inorder, and postorder differ in one thing only — when you visit the current node relative to its two subtrees. That one choice changes everything about what the output means.
After this lesson
You should be able to
- Write recursive preorder, inorder, and postorder traversals.
- Explain why inorder produces sorted output on a BST.
- Traverse level by level using a queue.
Try it before you read
Try it live
Empty tree — insert a value to begin.
One choice, three orders
Every one of these traversals visits the left subtree, the current node, and the right subtree. The only thing that changes is when the current node gets visited relative to the two subtrees: before both (preorder), between them (inorder), or after both (postorder).
Preorder answers 'announce yourself before your team' — visit a manager before either of their reports, which is why preorder is how you would print an org chart top-down. Postorder answers 'finish your team's work before reporting up' — visit both children before the node itself, which is exactly the order you must free a tree's memory in, since you cannot free a parent while a child still needs to be reached through it.
void preorder(struct Node *n) {
if (n == NULL) return;
printf("%d ", n->data); /* visit first */
preorder(n->left);
preorder(n->right);
}
void inorder(struct Node *n) {
if (n == NULL) return;
inorder(n->left);
printf("%d ", n->data); /* visit in the middle */
inorder(n->right);
}
void postorder(struct Node *n) {
if (n == NULL) return;
postorder(n->left);
postorder(n->right);
printf("%d ", n->data); /* visit last */
}Inorder's special payoff, on a BST
On a binary search tree specifically — which Lesson 4 defines precisely — inorder traversal always lists values in sorted order. That is not a coincidence: 'left, then me, then right' visits everything smaller than the current node before it and everything bigger after it, at every single node, which is exactly the sorted-order guarantee.
This is worth trying yourself below before Lesson 4 explains why. Insert a handful of values in any order you like, then click Inorder.
Level order: visiting rank by rank, with a queue
All three traversals above go deep before they go wide — they are depth-first. Sometimes you want breadth-first instead: visit the root, then every node at depth 1, then every node at depth 2, and so on — exactly how you would read an org chart rank by rank.
This is Unit I's queue, doing real work: enqueue the root, then repeatedly dequeue a node, visit it, and enqueue its children. FIFO order guarantees rank-by-rank output for exactly the same reason a queue kept round-robin service fair back in Unit I — first in, first served.
void level_order(struct Node *root)
{
if (root == NULL) return;
struct Node *queue[100];
int front = 0, rear = -1, count = 0;
rear = 0; queue[0] = root; count = 1;
while (count > 0) {
struct Node *n = queue[front];
front = (front + 1) % 100;
count--;
printf("%d ", n->data);
if (n->left) { rear = (rear + 1) % 100; queue[rear] = n->left; count++; }
if (n->right) { rear = (rear + 1) % 100; queue[rear] = n->right; count++; }
}
}Try it yourself
Using the tree below the lesson, insert 50, 30, 70, 20, 40 in that order, then predict all three depth-first traversal outputs before clicking each button to check.
Need a hint?
Preorder always starts with the root. Inorder always ends up sorted on a BST. Postorder always ends with the root.
Check the worked solution
Preorder: 50, 30, 20, 40, 70 — root first, then the left subtree completely, then the right. Inorder: 20, 30, 40, 50, 70 — sorted, exactly as promised. Postorder: 20, 40, 30, 70, 50 — root last. Getting these three predictions right by hand, before the widget confirms them, is the actual exercise — the widget is the answer key, not the practice.
Quick check
Why does inorder traversal produce sorted output on a binary search tree?
Why this lesson exists
Syllabus mapping
traversing a Binary Tree
Maps to course outcomes CO1, CO4.