Tree Traversals
Preorder, inorder, and postorder DFS, plus level-order BFS - the four ways to visit every node, and when each one is the right tool.
On this page
Trees are where recursion stops being a party trick and becomes the natural way to think. A binary tree is a set of nodes where each has up to two children (left and right), and almost every tree problem starts with one question: in what order do you visit the nodes? There are four answers, and knowing which to reach for is half the battle.
The four traversals
Three are depth-first (go deep before wide), distinguished by when you process the current node relative to its children; the fourth is breadth-first (level by level):
- Preorder - node, then left, then right. (Process the root first.)
- Inorder - left, then node, then right. (For a BST, this yields sorted order.)
- Postorder - left, then right, then node. (Process children before the parent - good for deletion and computing sizes.)
- Level-order - top to bottom, left to right, using a queue (BFS).
root → left → right
Depth-first, recursively
The three DFS orders differ by a single line - where you visit the node:
void preorder(TreeNode n) {
if (n == null) return;
visit(n); // node first
preorder(n.left);
preorder(n.right);
}
void inorder(TreeNode n) {
if (n == null) return;
inorder(n.left);
visit(n); // node in the middle
inorder(n.right);
}
void postorder(TreeNode n) {
if (n == null) return;
postorder(n.left);
postorder(n.right);
visit(n); // node last
}The recursion mirrors the tree's structure exactly, which is why tree code is so compact. The base case is always "null node → return," and the recursion always fans out to the children.
Breadth-first with a queue
Level-order can't be done by simple recursion - it needs a queue (the FIFO structure from the linked-structures module) to process nodes in discovery order:
// level-order (BFS): visit the tree level by level
void levelOrder(TreeNode root) {
if (root == null) return;
Deque<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode n = queue.poll();
visit(n);
if (n.left != null) queue.offer(n.left);
if (n.right != null) queue.offer(n.right);
}
}Which traversal for which problem
Use inorder on a BST to get values in sorted order. Use postorder when a node's result depends on its children (height, subtree size, deleting a tree). Use preorder to copy or serialize a tree top-down. Use level-order for anything about depth, levels, or 'nearest' - like the minimum depth or a right-side view.
An org chart is a tree, and how you 'read' it depends on your goal. Announce the CEO, then walk down each department fully before moving to the next - that's preorder (top-down). Tally every employee's report count before their manager's, so a manager's total includes their team - that's postorder (children first). List everyone by rank, all VPs before all directors before all managers - that's level-order. Same chart, different reading order for different questions.
A binary search tree keeps smaller values on the left and larger on the right of every node. Explain why an inorder traversal (left, node, right) visits the values in ascending sorted order.
Which traversal of a binary search tree visits values in ascending sorted order?
Key takeaways
- The four traversals are preorder (node,left,right), inorder (left,node,right), postorder (left,right,node), and level-order (BFS).
- DFS traversals differ only in where you visit the node relative to recursing into the children.
- Inorder on a BST yields sorted order; postorder processes children before the parent; preorder is top-down.
- Level-order needs a queue (FIFO) to process nodes by level - use it for depth/level/'nearest' problems.
- Tree recursion mirrors the tree's structure: base case is a null node, recursion fans out to children.