Traversals
In-order, pre-order, post-order.
Traversals is a free C Academy lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the C Academy learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
What Is a Traversal?
A traversal is a systematic way to visit every node in a tree exactly once.
The three classic depth-first orders are in-order, pre-order, and post-order. They differ only in when the current node is processed relative to its subtrees.
In-Order Traversal
In-order visits the left subtree, then the node, then the right subtree.
For a BST this prints values in sorted ascending order, which makes it the most useful traversal for search trees.
void in_order(Node *root) {
if (root == NULL) return;
in_order(root->left);
printf("%d ", root->value);
in_order(root->right);
}Pre-Order Traversal
Pre-order visits the node first, then the left subtree, then the right subtree.
It is handy for copying a tree or producing a prefix expression, because the root is emitted before its children.
void pre_order(Node *root) {
if (root == NULL) return;
printf("%d ", root->value);
pre_order(root->left);
pre_order(root->right);
}Post-Order Traversal
Post-order visits both subtrees first, then the node last.
Because children are handled before their parent, this order is exactly what you need when freeing a tree, so a node is never used after its children are gone.
void post_order(Node *root) {
if (root == NULL) return;
post_order(root->left);
post_order(root->right);
printf("%d ", root->value);
}The Common Pattern
All three depth-first traversals share the same skeleton: a NULL base case, a recursion into the left child, a recursion into the right child, and a visit step.
Only the position of the visit step changes the order's name.
/* visit position decides the order:
* pre : VISIT, left, right
* in : left, VISIT, right
* post : left, right, VISIT
*/In-Order Prints Sorted
This program builds a small BST and runs an in-order traversal, demonstrating the sorted output property.
The values come out from smallest to largest regardless of the insertion order.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
Node *insert(Node *r,int v){
if(!r) return cn(v);
if(v<r->value) r->left=insert(r->left,v);
else if(v>r->value) r->right=insert(r->right,v);
return r;
}
void in_order(Node *r){ if(!r) return; in_order(r->left); printf("%d ", r->value); in_order(r->right); }
int main(void){
Node *root=NULL;
int d[]={10,5,15,3,7,12};
for(int i=0;i<6;i++) root=insert(root,d[i]);
in_order(root);
printf("\n");
return 0;
}Comparing the Three Orders
For the tree with root 10, left 5, right 15, the outputs differ:
Pre-order gives 10 5 15. In-order gives 5 10 15. Post-order gives 5 15 10. The node values are the same; only the visit timing changes.
/* 10
* / \
* 5 15
* pre : 10 5 15
* in : 5 10 15
* post: 5 15 10
*/Level-Order Traversal
Breadth-first, or level-order, visits nodes level by level from top to bottom. It is not naturally recursive; it uses a queue.
We enqueue the root, then repeatedly dequeue a node, print it, and enqueue its children.
void level_order(Node *root) {
if (!root) return;
Node *queue[100];
int head = 0, tail = 0;
queue[tail++] = root;
while (head < tail) {
Node *n = queue[head++];
printf("%d ", n->value);
if (n->left) queue[tail++] = n->left;
if (n->right) queue[tail++] = n->right;
}
}Traversal Drives Real Work
Traversals are templates for any operation that must touch every node, not just printing.
Swap the visit step for summing values, finding a maximum, or copying nodes, and the same structure does the job.
int sum_tree(Node *root) {
if (root == NULL) return 0;
return root->value
+ sum_tree(root->left)
+ sum_tree(root->right);
}Cost of a Traversal
Every traversal visits each node once, so it runs in time proportional to n, the number of nodes.
The recursion uses stack space proportional to the tree's height, which is log(n) when balanced and n in the worst case.
All Three at Once
This program prints pre-order, in-order, and post-order for the same tree so you can compare them side by side.
Watch how only the position of the print call changes the resulting sequence.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
void pre(Node *r){ if(!r) return; printf("%d ", r->value); pre(r->left); pre(r->right); }
void ino(Node *r){ if(!r) return; ino(r->left); printf("%d ", r->value); ino(r->right); }
void post(Node *r){ if(!r) return; post(r->left); post(r->right); printf("%d ", r->value); }
int main(void){
Node *root = cn(10);
root->left = cn(5); root->right = cn(15);
pre(root); printf("\n");
ino(root); printf("\n");
post(root); printf("\n");
return 0;
}Quick Check
Pick the right traversal for the job.
Recap
Depth-first traversals share one recursive skeleton; the visit step's position makes them pre-, in-, or post-order. In-order on a BST yields sorted output, and post-order is the safe order for freeing.
Level-order is breadth-first and uses a queue. All visit each node once in O(n) time.
Frequently asked questions
Is the “Traversals” lesson free?
Yes — the full text of “Traversals” is free to read here on the web, and the C Academy course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the C Academy course, upgrade to CoddyKit PRO.
What will I learn in “Traversals”?
In-order, pre-order, post-order. You practise C Academy with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start C Academy?
No prior experience is required. C Academy on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Traversals” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this C Academy lesson?
Yes. Every C Academy lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.