Tree Traversals

Preorder, inorder, postorder and level order: how each one walks a binary tree, how to write them with recursion, a stack or a queue, and which order each problem needs.

Overview

A traversal visits every node of a tree exactly once. Almost every tree problem is a traversal with some work done at each node, so the real skill is choosing the order in which the nodes are visited. There are four orders worth knowing: three depth-first orders (preorder, inorder, postorder) and one breadth-first order (level order).

Four orders, one tree

Every example on this page uses the same seven-node tree.

Preorder — node, then left subtree, then right subtree — 1, 2, 4, 5, 3, 6, 7 — copying or serializing a tree, top-down work
Inorder — left subtree, then node, then right subtree — 4, 2, 5, 1, 6, 3, 7 — binary search trees, where it gives sorted order
Postorder — left subtree, then right subtree, then node — 4, 5, 2, 6, 7, 3, 1 — heights, sizes, sums and other bottom-up work
Level order — one level at a time, left to right — [1], [2, 3], [4, 5, 6, 7] — anything about levels, depth or the nearest node

The three depth-first orders differ in one line

Depth-first search (DFS) goes down as far as it can before it backs up. The three DFS orders are the same recursive function. The only difference is where the line that handles the current node sits: before the two recursive calls, between them, or after them.

The trace shows preorder on the sample tree. Each row is one call. The output column grows only when a call reaches slot 1.

1 — 1 — visit 1, go left — 1
2 — 2 — visit 2, go left — 1, 2
3 — 4 — visit 4; both children are None — 1, 2, 4
4 — 5 — back at 2, go right; visit 5 — 1, 2, 4, 5
5 — 3 — back at 1, go right; visit 3 — 1, 2, 4, 5, 3
6 — 6 — visit 6 — 1, 2, 4, 5, 3, 6
7 — 7 — visit 7 — 1, 2, 4, 5, 3, 6, 7

For postorder the same calls happen in the same order, but a node is written down only after both of its children have finished. That is why postorder is the order for bottom-up answers: when you handle a node, the answers for both subtrees are already known.

Inorder with an explicit stack

The recursive version relies on the call stack, and an iterative version uses a stack you manage yourself. For inorder, the loop is: walk left as far as possible, pushing every node; pop one node and visit it; then move to its right child and repeat.

1 — 1 — [1, 2, 4] — 4 — None (4 has no right child)
2 — None — [1, 2] — 2 — 5
3 — 5 — [1, 5] — 5 — None
4 — None — [1] — 1 — 3
5 — 3 — [3, 6] — 6 — None
6 — None — [3] — 3 — 7
7 — 7 — [7] — 7 — None, stack empty: stop

Output: 4, 2, 5, 1, 6, 3, 7, the same as the recursive version. Iterative preorder is simpler: push the root, then pop a node, visit it, and push its right child and then its left child, so the left one comes out first.

Level order with a queue

Breadth-first search (BFS) uses a queue. Put the root in. Each round, read the queue's current size: those nodes are exactly one level. Remove that many nodes, record them, and add their children.

1 — [1] — [1] — [2, 3]
2 — [2, 3] — [2, 3] — [4, 5, 6, 7]
3 — [4, 5, 6, 7] — [4, 5, 6, 7] — []

Freezing the size at the start of a round is what separates the levels. Without it, children get mixed into the level of their parents. The queue must remove from the front in O(1): Python's collections.deque does, while list.pop(0) shifts every remaining element.

Several classic problems are level order with a small twist.

Right Side View — keep only the last node recorded in each round
Zigzag Level Order — reverse every second level before saving it
Minimum Depth — stop at the first leaf you dequeue
Average of Levels — average the values recorded in each round

Morris traversal: inorder in O(1) extra space

Both recursion and the explicit stack use O(h) memory, where h is the height. Morris traversal uses none. It stores the way back in the tree itself: before going left from a node, it makes the rightmost node of the left subtree (the node's inorder predecessor) point back to the node. When the walk later climbs back along that link, it removes the link, so the tree is unchanged at the end.

The trace uses a three-node tree: root 2, left child 1, right child 3.

1 — 2 — yes — 1, right is None — thread 1 to 2, go left
2 — 1 — no — visit 1, follow right (the thread) to 2 — 1
3 — 2 — yes — 1, right is 2 (the thread) — remove thread, visit 2, go right — 1, 2
4 — 3 — no — visit 3, right is None — 1, 2, 3
5 — None — stop — 1, 2, 3

Every edge is walked at most a few times, so the time is still O(n). Mention Morris traversal when O(1) space is required; write it only if asked, and say that it changes the tree while it runs, which is unsafe if another reader shares the tree.

Rebuilding a tree from two orders

A preorder list and an inorder list of the same tree, with distinct values, fix the tree completely. The first preorder value is the root. Find it in the inorder list: everything to its left is the left subtree, everything to its right is the right subtree. Recurse on both halves. A hash map from value to inorder index makes each lookup O(1), so the whole build is O(n).

1 — 1, 2, 4, 5, 3, 6, 7 — 4, 2, 5, 1, 6, 3, 7 — 1 — 4, 2, 5 — 6, 3, 7
2 — 2, 4, 5 — 4, 2, 5 — 2 — 4 — 5
3 — 3, 6, 7 — 6, 3, 7 — 3 — 6 — 7

Postorder plus inorder works the same way; the root is the last postorder value. Preorder plus postorder is not enough on its own. A root with a single child gives the same two lists whether that child is on the left or on the right, so the tree cannot be told apart.

1 with left child 2 — 1, 2 — 2, 1
1 with right child 2 — 1, 2 — 2, 1

Cost and the depth problem

Recursive DFS — O(n) — O(h) call stack — a very deep tree can exceed the recursion limit
Iterative DFS with a stack — O(n) — O(h) — more code
BFS with a queue — O(n) — O(w), the widest level — the last level of a full tree holds about half the nodes
Morris — O(n) — O(1) — changes the tree while running

The height h is about log2(n) for a balanced tree but n for a chain. Python stops recursion at a fixed depth (the default limit is 1000 on Python 3.14), so a skewed tree with a few thousand nodes crashes the recursive version. The stack version is the usual fix.

What you will be able to do

Write preorder, inorder and postorder by hand, recursively and with a stack, and say which slot the visit line sits in.
Write level order with a queue and adapt it to right-side view, zigzag and per-level statistics.
Rebuild a tree from preorder and inorder, and explain why preorder and postorder alone are not enough.
Explain Morris traversal and when O(1) space is worth its cost.
Pick the order a problem needs and state the time and space cost.

When to use it

Any problem that must look at every node of a tree
Level order (BFS) when the problem mentions levels, depth, width or the nearest node
Inorder when the tree is a BST and sorted order is useful
Preorder for copying, serializing or printing a tree top-down
Postorder when each node needs answers from its children first: height, size, diameter, subtree sums
Right side view, zigzag and other per-level views

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio