AdvancedData Structures & Algorithms · Lesson 25 of 25 · Updated ·
Tree Traversals — Preorder, Inorder, Postorder and Level Order
A binary tree is made of nodes; each node has a value and up to two children, left and right. Almost every tree problem — height, sum, mirror, path, serialise, validate a BST — is "visit every node in the right order and do something". There are four orders worth knowing by heart.
1. One tree, four orders
The three depth-first orders all go left before right. They differ only in when the root is visited:
- Preorder — root, left, right. (Root first: copying a tree, printing a folder structure.)
- Inorder — left, root, right. (In a binary search tree this gives the values sorted.)
- Postorder — left, right, root. (Root last: deleting a tree, computing sizes and heights from the children up.)
Level order is breadth-first: level by level, left to right, using a queue.
2. Recursive traversals
class Node:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
root = Node(1, Node(2, Node(4), Node(5)), Node(3, None, Node(6)))
def preorder(n, out):
if n:
out.append(n.val); preorder(n.left, out); preorder(n.right, out)
return out
def inorder(n, out):
if n:
inorder(n.left, out); out.append(n.val); inorder(n.right, out)
return out
def postorder(n, out):
if n:
postorder(n.left, out); postorder(n.right, out); out.append(n.val)
return out
print(preorder(root, []))
print(inorder(root, []))
print(postorder(root, []))
[1, 2, 4, 5, 3, 6]
[4, 2, 5, 1, 3, 6]
[4, 5, 2, 6, 3, 1]
Every node is visited once: O(n) time. The recursion uses O(h) stack space, where h is the height — O(log n) for a balanced tree, but O(n) for a tree that is one long chain.
3. Level order (BFS)
Take nodes from the front of a queue; add their children at the back. Process one level at a time by reading the queue's length at the start of each level.
class Node:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
root = Node(1, Node(2, Node(4), Node(5)), Node(3, None, Node(6))) # the tree in the diagram
from collections import deque
def level_order(root):
levels, q = [], deque([root] if root else [])
while q:
level = []
for _ in range(len(q)): # exactly the nodes of this level
n = q.popleft()
level.append(n.val)
if n.left: q.append(n.left)
if n.right: q.append(n.right)
levels.append(level)
return levels
print(level_order(root))
print([lvl[-1] for lvl in level_order(root)]) # right side view
[[1], [2, 3], [4, 5, 6]]
[1, 3, 6]
Many problems are tiny changes to this loop: right side view (last of each level), level averages, zigzag order (reverse every other level), minimum depth (stop at the first leaf).
4. Iterative traversals with an explicit stack
Interviewers sometimes forbid recursion (or the tree is so deep that recursion would overflow). Inorder with a stack: go left as far as possible, pushing nodes; then pop one, visit it, and move to its right child.
class Node:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
root = Node(1, Node(2, Node(4), Node(5)), Node(3, None, Node(6))) # the tree in the diagram
def inorder_iterative(root):
out, stack, n = [], [], root
while n or stack:
while n: # go as far left as possible
stack.append(n)
n = n.left
n = stack.pop()
out.append(n.val) # visit
n = n.right # then the right subtree
return out
def preorder_iterative(root):
out, stack = [], [root] if root else []
while stack:
n = stack.pop()
out.append(n.val)
if n.right: stack.append(n.right) # push right first, so left is popped first
if n.left: stack.append(n.left)
return out
print(inorder_iterative(root))
print(preorder_iterative(root))
[4, 2, 5, 1, 3, 6]
[1, 2, 4, 5, 3, 6]
5. Postorder thinking: answers built from the children
Many questions are "compute something for each node from its children's answers" — that is postorder. Height is the classic:
class Node:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
root = Node(1, Node(2, Node(4), Node(5)), Node(3, None, Node(6))) # the tree in the diagram
def height(n):
if not n:
return 0
return 1 + max(height(n.left), height(n.right))
def count_leaves(n):
if not n:
return 0
if not n.left and not n.right:
return 1
return count_leaves(n.left) + count_leaves(n.right)
print(height(root), count_leaves(root))
3 3
The same shape solves diameter, balanced-tree check, maximum path sum and subtree sums: get the left answer, get the right answer, combine at the node.
Inorder and level order in Java
import java.util.*;
public class Main {
static class Node {
int val; Node left, right;
Node(int v, Node l, Node r) { val = v; left = l; right = r; }
Node(int v) { this(v, null, null); }
}
static void inorder(Node n, List<Integer> out) {
if (n == null) return;
inorder(n.left, out); out.add(n.val); inorder(n.right, out);
}
static List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> levels = new ArrayList<>();
Queue<Node> q = new ArrayDeque<>();
if (root != null) q.offer(root);
while (!q.isEmpty()) {
List<Integer> level = new ArrayList<>();
for (int size = q.size(); size > 0; size--) {
Node n = q.poll();
level.add(n.val);
if (n.left != null) q.offer(n.left);
if (n.right != null) q.offer(n.right);
}
levels.add(level);
}
return levels;
}
public static void main(String[] args) {
Node root = new Node(1, new Node(2, new Node(4), new Node(5)), new Node(3, null, new Node(6)));
List<Integer> in = new ArrayList<>();
inorder(root, in);
System.out.println(in);
System.out.println(levelOrder(root));
}
}
[4, 2, 5, 1, 3, 6]
[[1], [2, 3], [4, 5, 6]]
6. Which traversal for which problem?
| Problem | Traversal |
|---|---|
| Print a BST in sorted order, k-th smallest, validate a BST | inorder |
| Copy / serialise a tree, print a directory tree | preorder |
| Height, diameter, delete a tree, subtree sums | postorder |
| Level averages, right side view, minimum depth, zigzag | level order (BFS) |
Common mistakes
- Forgetting the base case
if not n— the recursion crashes onNone. - Taking
len(q)inside the inner loop in level order — the queue grows while you loop, so levels mix. Read it once per level. - In iterative preorder, pushing the left child first — then the right subtree is visited first.
- Assuming recursion depth is fine for 10⁵ nodes in a chain — Python's default limit is about 1000; use an iterative version.
Quick recap
- Preorder = root, left, right; inorder = left, root, right; postorder = left, right, root.
- Level order = BFS with a queue, one level per outer loop.
- All four are O(n) time; recursion uses O(h) extra space.
- Inorder of a BST is sorted; postorder builds answers from the children up.