Binary tree traversals

Most engineers learn binary tree traversal as three separate algorithms to memorize. Preorder, inorder, postorder. But they aren't separate algorithms. They're the same recursive structure with one line of code moved to a different position. That one-line difference changes what you can compute and which problems you can solve in interviews.

What binary tree traversal actually is

Binary tree traversal is the process of visiting every node in a binary tree exactly once, following a defined order. The four standard types are preorder (root, left, right), inorder (left, root, right), postorder (left, right, root), and level order (left to right, level by level). Each exposes different information about the tree's shape and relationships.

That definition appears everywhere. What it doesn't tell you is why four orders exist instead of one.

Different orders let you access different information at the moment you process a node. In preorder, you process the root before its children. You have the parent's data available as you descend, which makes it useful for copying a tree, serializing it, or passing accumulated state downward.

In inorder, you process the left subtree, then the root, then the right. On a binary search tree, this produces nodes in sorted order. The sorting is a direct consequence of the BST invariant (left < root < right). On a general binary tree without the BST property, inorder gives you left-root-right ordering, but the values won't be sorted.

In postorder, you process both children before the root. You have the results from the entire subtree available when you finally reach the parent. Height, diameter, and subtree-sum problems all use postorder because you need the children's answers first. Level order is the outlier. You process nodes left to right, one level at a time, using a queue instead of recursion. It's the only traversal that isn't depth-first.

Four binary tree traversals on one tree

Run all four on the same tree and the difference becomes obvious.

`        1
       / \
      2   3
     / \   \
    4   5   6
   /
  7
`

1. Preorder

(root, left, right) visits the root first, then recurses left, then right. On our example tree, that gives 1, 2, 4, 7, 5, 3, 6.

You see the root immediately. Every parent appears before its children, which is exactly what tree serialization needs. You can reconstruct the tree from a preorder sequence (given null markers or an inorder companion) because the root always comes first.

2. Inroder

(left, root, right) recurses all the way left, processes the node, then goes right. The output is 7, 4, 2, 5, 1, 3, 6.

On a BST, this trace would be sorted. On this tree (which isn't a BST), it still follows the left-root-right structure, but the values aren't ordered. The sorting property only kicks in when the tree's values obey the BST invariant, so don't assume "inorder = sorted" unless you've confirmed you're working with a BST.

3. Postorder

(left, right, root) processes both children before the parent, giving 7, 4, 5, 2, 6, 3, 1. The root appears last. Every parent appears after all its descendants. So if the parent needs information from its children's results, postorder is the right choice. You'll see this come up repeatedly in interview problems: height, diameter, subtree sums, balanced tree checks. The common thread is always "I can't answer the parent's question until both children have reported back."

4. Level order

(BFS) processes all nodes at depth 0, then depth 1, then depth 2, producing 1, 2, 3, 4, 5, 6, 7.

Level order uses a queue, not recursion. Enqueue the root, then repeatedly dequeue a node and enqueue its children. The queue naturally processes nodes in breadth-first order. Compare that to the three DFS traversals, which differ only by where process(node) sits relative to the recursive calls:

Why traversal order determines what you can compute

This isn't academic trivia. In interviews, choosing the wrong traversal order means you can't solve the problem. Take height of a binary tree. To compute the height of a node, you need the heights of both its children first. Left child height, right child height, take the maximum, add one. Postorder, where children get processed before the parent.

If you tried preorder, you'd reach the root with no information about the subtree below. You'd have to pass depth downward as a parameter and track the maximum globally. It works, but it's awkward compared to the postorder version that returns height naturally through the recursion.

Trace the height computation on our earlier tree to see this in action.

`
Node 7: no children             -> height 0
Node 4: left(7) = 0, no right   -> max(0, -1) + 1 = height 1
Node 5: no children             -> height 0
Node 2: left(4) = 1, right(5) = 0 -> max(1, 0) + 1 = height 2
Node 6: no children             -> height 0
Node 3: no left, right(6) = 0   -> max(-1, 0) + 1 = height 1
Node 1: left(2) = 2, right(3) = 1 -> max(2, 1) + 1 = height 3
`

Each node computes its height only after its children have been processed. That's the postorder invariant, children first, parent last. Problems like tree diameter, subtree sums, distributing coins, and balanced tree checks all follow this same dependency pattern.

Some problems can be solved with multiple traversal orders. Computing height with preorder is possible, as mentioned. But the postorder version is five lines. The preorder version is fifteen. Picking the natural traversal order matters beyond correctness. Interviewers notice when someone reaches for the right traversal immediately versus wrestling it into shape.

Level order follows the same logic. Anything that operates on nodes at the same depth (level sums, zigzag traversal, connecting nodes at the same level) needs breadth-first access. Depth-first traversal doesn't naturally group nodes by level, so forcing it requires extra bookkeeping. For a deeper comparison of when BFS and DFS are the right choice across trees and graphs, see the BFS vs DFS guide.

Recursion vs iteration: When the stack matters

The recursive versions are clean. Three lines plus a base case. So why would you ever write iterative traversals?

Deep trees can overflow the call stack. A tree with 10,000 levels of left-only children will crash a recursive traversal in most languages. The iterative version manages the stack explicitly with a list, using heap memory instead of stack frames. Python's default recursion limit is 1,000. Java's stack depth depends on the JVM settings but typically caps out around 5,000-10,000 frames. In competitive programming and interview settings, you'll hit these limits on skewed trees, which is exactly the kind of edge case that separates a "works on examples" solution from a correct one.

Interviewers also ask for iterative implementations specifically. They're testing whether you understand that recursion uses an implicit stack and whether you can make that stack explicit.

Iterative preorder is the simplest conversion. Push the root onto a stack, pop and process, then push right before left so that left gets processed first.

Iterative inorder is slightly more involved. Keep pushing left children until you hit None, then pop and process, then move right.

Iterative postorder is the trickiest. You need to process children before their parent, but you encounter the parent first. Writing iterative postorder correctly under time pressure shows you genuinely understand the relationship between recursion and stack frames.

Codeintuition's Binary Tree course covers all three iterative implementations with frame-by-frame visual walkthroughs that trace the stack state at each step. Reading the code alone won't get you there for iterative traversals. You need to watch the stack grow and shrink across 8-10 frames until the pattern clicks. The iterative inorder pattern in particular looks confusing on paper, but once you've traced the stack through a 7-node tree twice, the "push left, pop, go right" rhythm becomes second nature.

Common binary tree traversal mistakes

The patterns built on top

Every tree problem in interviews starts with picking a traversal order. The patterns built on top of these four orders are where the real interview complexity lives. Stateless preorder, stateful preorder, stateless postorder, stateful postorder, root-to-leaf path, level order, lowest common ancestor, simultaneous traversal. Eight distinct pattern families, each with its own set of problems, and each rooted in the same four traversal orders you've just seen.

For a complete walkthrough of how these patterns connect and when each applies, see our guide on trees, recursion, and mental models.

Codeintuition's learning path covers 47 lessons and 62 problems in the Binary Tree course alone. The recursive and iterative traversal fundamentals are covered before any pattern-based problem practice begins. You build the traversal intuition first, then apply it across eight distinct pattern families.

Listing the four traversal types is the easy part. Looking at a tree problem you haven't seen and immediately knowing which order gives you the information you need is the hard part. That recognition comes from understanding why each order exists, not from memorizing traces.