Binary Tree Traversals

Preorder, inorder, postorder, and level-order — four traversal orders that visit every node, and the recursive-to-iterative pattern you must know for interviews.

12 min readLeetCode Patterns for InterviewsCode

The Pattern

Tree traversal means visiting every node exactly once. The three depth-first orders (preorder, inorder, postorder) differ only in when you process the root relative to its left and right subtrees. Level-order (BFS) processes nodes level by level using a queue. The recursive form is elegant, but the iterative stack version is essential for interviews — it mirrors the call stack explicitly and avoids overflow.

Binary tree — preorder visits root, then left, then right

Preorder: 1→2→4→5→3→6. Inorder: 4→2→5→1→6→3. Postorder: 4→5→2→6→3→1. Level-order: 1→2→3→4→5→6. The only difference is the position of the root visit.

Gorecursive-template-—-all-three-orders-in-six-lines.go

24 linesLn 1, Col 1Go

The three recursive orders are identical except for the placement of visit(root). Moving it before, between, or after the two recursive calls changes the traversal order.

Recursive vs Iterative

Recursive traversals are concise but use O(h) call-stack memory, risking overflow on skewed trees (h = n). Iterative traversals replace the call stack with an explicit heap-allocated stack, giving you full control.

Goiterative-inorder-—-the-universal-dfs-pattern.go

17 linesLn 1, Col 1Go

The inner loop pushes every left ancestor onto the stack. When we pop, we visit the node and then explore its right subtree. This exactly mimics recursive inorder.

Aspect	Recursive	Iterative
Code length	~3 lines	~12 lines
Memory	O(h) call stack	O(h) explicit stack (heap)
Overflow risk	Yes (deep/skewed tree)	No
Early exit	Awkward (panic/return)	Trivial (break loop)
Preorder variant	visit before calls	Push right, then left

When to Use

Preorder: clone a tree, serialize/deserialize, prefix expression evaluation.
Inorder: BST yields sorted order (most common tree interview pattern).
Postorder: delete tree, postfix evaluation, compute subtree properties bottom-up.
Level-order: shortest path, right-side view, connect siblings, or any BFS need.

The visit placement is everything

Preorder processes the root before its children (top-down), postorder processes after children (bottom-up), and inorder interleaves between left and right subtrees. This single-line difference — where visit(root) appears — controls the entire traversal.

Problems

#144Binary Tree Preorder TraversalEasyDFS preorder · O(n) time · O(n) space #94Binary Tree Inorder TraversalEasyDFS inorder · O(n) time · O(n) space #102Binary Tree Level Order TraversalMediumBFS with queue · O(n) time · O(n) space

Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.

Stage 1 · Code

Linked Lists & Trees