Tree traversals
easyThe three depth-first orders run the same two recursive calls; all that changes is where visit sits. Swap the stack for a queue and depth-first becomes breadth-first.
O(n)Space O(h) for the stackWhat to notice
The three depth-first orders differ by one line's position
Pre, in and post-order run the same two recursive calls; all that changes is whether visit happens before, between or after them. Everything else about their behaviour follows from that placement.
In-order on a BST emits sorted output
Left subtree holds smaller keys, right holds larger, so visiting left-self-right is exactly ascending order. That is a free O(n) sort, and the reason 'validate a BST' is usually solved with an in-order walk.
Stack means depth-first, queue means breadth-first
The only structural difference between DFS and BFS is which container holds the pending nodes. Swap the stack for a queue and depth-first becomes level-order - the identical insight that separates DFS from BFS on graphs.
Each order has a job
Pre-order serialises a tree (you need the parent before its children). Post-order frees or evaluates one (children must be done first). In-order sorts. Level-order finds the shallowest anything.
Saved in this browser - no sign-up, nothing sent anywhere.
How tree traversals work
All three depth-first orders are one function. Recurse into node.left, recurse into node.right, and place the visit call before, between, or after those two calls - that single choice of position is the whole difference between pre-order, in-order, and post-order. Each placement has a job: pre-order reaches a parent before its children, post-order finishes the children first, in-order lands exactly between the two halves.
In-order carries a guarantee worth memorising: on a binary search tree it emits keys in ascending order. Everything in node.left is smaller and everything in node.right is larger, so visiting left, self, right is a sorted walk - a free O(n) sort. That is why validating a BST and finding the k-th smallest key are both usually solved with an in-order pass.
The iterative version swaps the call stack for an explicit one and changes nothing else: push nodes while diving left, pop to visit, then turn right. Replace that stack with a queue and depth-first becomes level-order - nodes come out nearest-first. Which container holds the pending work is the only structural difference between DFS and BFS, on trees and graphs alike.
Step by step
- Insert 50, 30, 70, 20, 40 into a BST: 50 becomes the root, 30 its left child holding 20 and 40, 70 its right child.
- inorder(50) immediately recurses into inorder(30) - no node may be visited until its entire left subtree is finished.
- inorder(30) recurses into 20 first. 20 has no left child, so 20 becomes the first key visited.
- Back at 30: its left subtree is done, so visit 30, then recurse into its right child and visit 40.
- The root's left subtree is now complete. Visit 50, then descend into the right subtree.
- 70 has no children, so it is visited last. Output: 20, 30, 40, 50, 70 - ascending, exactly as a BST guarantees.
Complexity
| Worst case time | O(n) |
|---|---|
| Space | O(h) for the stack |
Reference implementation
Python
def inorder(node, out=None):
"""Left, self, right. On a BST this emits sorted order."""
out = [] if out is None else out
if node:
inorder(node.left, out)
out.append(node.key)
inorder(node.right, out)
return out
def inorder_iterative(root):
"""Same output, explicit stack, no recursion limit to hit."""
out, stack, cur = [], [], root
while cur or stack:
while cur: # dive left as far as possible
stack.append(cur)
cur = cur.left
cur = stack.pop()
out.append(cur.key) # visit on the way back up
cur = cur.right
return out
def level_order(root):
"""Breadth-first: a queue instead of a stack."""
from collections import deque
out, q = [], deque([root] if root else [])
while q:
node = q.popleft()
out.append(node.key)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
return outJavaScript
function inorder(node, out = []) {
if (!node) return out;
inorder(node.left, out);
out.push(node.key);
inorder(node.right, out);
return out;
}
function inorderIterative(root) {
const out = [], stack = [];
let cur = root;
while (cur || stack.length) {
while (cur) { stack.push(cur); cur = cur.left; }
cur = stack.pop();
out.push(cur.key);
cur = cur.right;
}
return out;
}
function levelOrder(root) {
const out = [], q = root ? [root] : [];
while (q.length) {
const n = q.shift();
out.push(n.key);
if (n.left) q.push(n.left);
if (n.right) q.push(n.right);
}
return out;
}Java
static void inorder(Node n, List<Integer> out) {
if (n == null) return;
inorder(n.left, out);
out.add(n.key);
inorder(n.right, out);
}
static List<Integer> levelOrder(Node root) {
List<Integer> out = new ArrayList<>();
if (root == null) return out;
Queue<Node> q = new ArrayDeque<>();
q.add(root);
while (!q.isEmpty()) {
Node n = q.poll();
out.add(n.key);
if (n.left != null) q.add(n.left);
if (n.right != null) q.add(n.right);
}
return out;
}Common pitfalls
- Skipping the null check at the top of the recursion. Every leaf makes two calls with null children, and the empty-tree case shows up on day one.
- Recursing on a degenerate tree. Insert sorted keys and the calls nest n deep - Python's default limit of 1000 frames turns that into a crash. The explicit-stack version has no such ceiling.
- Visiting on push instead of on pop in the iterative version - that quietly produces pre-order when you meant in-order.
- Using a stack for level-order. Breadth-first needs a queue; a stack silently hands back depth-first order instead.
- Expecting in-order output to be sorted on any binary tree. The guarantee only holds where the BST property does.
Where it is used
- In-order: validating a BST, k-th smallest queries, and exporting an index in sorted order.
- Pre-order: serialising a tree to disk or over the wire - the parent must arrive before its children can be reattached.
- Post-order: freeing nodes, computing subtree sizes, and evaluating expression trees - children must finish before the parent.
- Level-order: printing a tree by depth, finding the shallowest match, and level-based interview problems like right-side view or zigzag order.
Frequently asked questions
What is the time and space complexity of tree traversal?
All four traversals are O(n) worst case - every node is visited exactly once. Space is O(h) for the stack, recursive or explicit, where h is the height: about log n on a balanced tree, n on a degenerate one. Level-order swaps that for a queue sized by the tree's width - roughly its widest level.
Which traversal prints a binary search tree in sorted order?
In-order. The BST property puts smaller keys in node.left and larger keys in node.right, so visiting left, self, right emits every key in ascending order. The other orders do not sort: pre-order starts from the root and post-order ends there, wherever those keys rank.
How do you traverse a tree without recursion?
Keep an explicit stack. For in-order: push nodes while walking left; when there is no left child, pop, visit, and switch to the popped node's right child. The output is identical to the recursive version - the stack just makes the call frames visible - and there is no recursion depth limit to hit.
What is the difference between DFS and BFS on a tree?
Only the container holding pending nodes. A stack - explicit or the call stack - dives deep before backing up: depth-first. A queue drains nodes in arrival order, level by level: breadth-first. Memory differs too: DFS holds one path, O(h), while BFS holds the widest level, which in a full tree is about n/2 nodes.