Tree Traversals
Preorder, inorder and postorder (depth-first, recursive) and level order (breadth-first, with a queue). Know them by hand and in code.
Rule of this site: Don't just watch: implement it yourself, then solve 2–3 problems.
02Mental model
You are visiting every room in a building. Depth-first means you go down one corridor to the end before trying the next. Breadth-first means you visit every room on floor 1 before going to floor 2.
The three depth-first orders
All three go left before right. They differ only in when you visit the node itself:
| Order | Rule | Memory trick |
|---|---|---|
| Preorder | Node, Left, Right | node comes pre (before) |
| Inorder | Left, Node, Right | node is in the middle |
| Postorder | Left, Right, Node | node comes post (after) |
void inorder(Node* r) {
if (!r) return;
inorder(r->left);
cout << r->data << " ";
inorder(r->right);
}Move the cout line up for preorder, down for postorder.
What each is good for
- Preorder: copying a tree, printing folder structures.
- Inorder: a BST in sorted order.
- Postorder: deleting a tree (children before parent), evaluating expression trees.
Level order (breadth-first)
Use a queue: push the root; repeatedly pop a node, print it, push its left and right children. The queue makes sure nodes come out level by level, left to right. This is BFS, which you will meet again on graphs in Chapter 7.
03Visualize
space play · ←→ step · r reset. The highlighted code line follows each step.
Run all four on the same tree. Watch the call stack for the DFS orders and the queue for level order.
04C++ code
Compiled and run with g++ -std=c++17; the output below is real. Type it out yourself before you copy it.
#include <iostream>
#include <queue>
using namespace std;
struct Node { int data; Node* left; Node* right; };
Node* insert(Node* r, int x) {
if (!r) return new Node{x, nullptr, nullptr};
if (x < r->data) r->left = insert(r->left, x);
else r->right = insert(r->right, x);
return r;
}
void preorder(Node* r) { if (!r) return; cout << r->data << " "; preorder(r->left); preorder(r->right); }
void inorder(Node* r) { if (!r) return; inorder(r->left); cout << r->data << " "; inorder(r->right); }
void postorder(Node* r) { if (!r) return; postorder(r->left); postorder(r->right); cout << r->data << " "; }
void levelOrder(Node* root) {
if (root == nullptr) return;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* cur = q.front(); q.pop();
cout << cur->data << " ";
if (cur->left) q.push(cur->left);
if (cur->right) q.push(cur->right);
}
}
void destroy(Node* r) { if (!r) return; destroy(r->left); destroy(r->right); delete r; } // postorder!
int main() {
Node* root = nullptr;
for (int x : {50, 30, 70, 20, 40, 60, 80}) root = insert(root, x);
cout << "preorder: "; preorder(root); cout << "\n";
cout << "inorder: "; inorder(root); cout << "\n";
cout << "postorder: "; postorder(root); cout << "\n";
cout << "level order: "; levelOrder(root); cout << "\n";
destroy(root);
}preorder: 50 30 20 40 70 60 80 inorder: 20 30 40 50 60 70 80 postorder: 20 40 30 60 80 70 50 level order: 50 30 70 20 40 60 80
05Complexity
| pre / in / post order | O(n): every node once |
|---|---|
| level order | O(n) |
| Extra space | O(h) recursion for DFS; O(w) queue for level order (w = widest level) |
All four visit every node exactly once. They only differ in when a node is printed.
06Watch
Binary tree traversal: Preorder, Inorder, Postorder
Why this one: Preorder, inorder, postorder with recursion, traced on a real tree.
Binary tree: Level Order Traversal
Why this one: Level order with a queue. This is the same idea as BFS in Chapter 7.
07Exam lens
Likely questions
- Give the preorder, inorder, postorder and level-order traversals of a drawn tree.
- Write recursive functions for preorder, inorder and postorder.
- Which traversal of a BST gives sorted output?
- Which data structure does level-order traversal use, and why?
- Given preorder and inorder sequences, rebuild the tree.
Common mistakes
- Mixing the orders. Remember where the Node goes - pre = N L R, in = L N R, post = L R N.
- Forgetting that "left before right" is the same in all three.
- Using a stack for level order (that gives a DFS order instead).
08Quick check
09Practice
🟢 Trace by hand
Using the BST from 50, 30, 70, 20, 40, 60, 80, 35: write all four traversals.
Show answer
- Preorder:
50 30 20 40 35 70 60 80 - Inorder:
20 30 35 40 50 60 70 80(sorted) - Postorder:
20 35 40 30 60 80 70 50 - Level order:
50 30 70 20 40 60 80 35
🟡 Implement it
Rebuild a tree from preorder A B D E C F and inorder D B E A F C, then write its postorder.
Hint
The first preorder item is the root. Find it in the inorder list; everything to its left is the left subtree. Repeat.
Solution
Root A. Inorder left D B E, right F C. Left root B (children D, E). Right root C (left child F).
Postorder: D E B F C A
🔴 Solve problems
Hint
Recursive first. Then try it with an explicit stack.
Hint
Same template, print before recursing.
Hint
Inside the queue loop, process
q.size()nodes at a time. That batch is one level.
10Mastery checklist
Tick these honestly. When every box is ticked, the topic is marked complete.