vault

Tree Traversals

11 min read

Tree Traversals

“Traversing” a tree means visiting every node exactly once in some defined order. For binary trees there are four canonical orders — pre-order, in-order, post-order (the three depth-first orders), and level-order (the breadth-first / BFS order). Each is naturally O(n) time and uses some auxiliary space (recursion stack or explicit data structure). Picking the right order for a problem is half the battle on tree problems; Morris traversal is the trick for O(1) space.

1. Intuition — Three Ways to Read a Family Tree

Imagine a family tree where each grandparent has two children, each of those has two children, etc. (a binary tree). You want to say everyone’s name — but in what order?

Three natural orders:

  • “Talk about the grandparent first, then the left-side family, then the right-side family” — Grandpa, Dad, Me, Sister, Uncle, Cousin1, Cousin2 — this is pre-order.
  • “Visit the left-side family first, then announce the grandparent, then the right-side family” — Me, Dad, Sister, Grandpa, Cousin1, Uncle, Cousin2 — this is in-order.
  • “Talk about both families first, then their parents, then the grandparent” — Me, Sister, Dad, Cousin1, Cousin2, Uncle, Grandpa — this is post-order.

The only difference between these three orders is when you announce the parent relative to its two children: before, between, or after.

The fourth order — level-order — is to walk floor-by-floor through the family-tree layout: grandparent, then both kids, then all four grandkids, etc.

2. Tiny Worked Example

        1
       / \
      2   3
     / \   \
    4   5   6
OrderSequence
Pre-order1, 2, 4, 5, 3, 6
In-order4, 2, 5, 1, 3, 6
Post-order4, 5, 2, 6, 3, 1
Level-order1, 2, 3, 4, 5, 6

Notice the position of 1 (the root) in each: first (pre), middle (in), last (post). For each subtree, the same rule applies recursively.

3. Recursive Definitions (Pseudocode)

preorder(node):
    if node == null: return
    visit(node)                 # ← "node first"
    preorder(node.left)
    preorder(node.right)

inorder(node):
    if node == null: return
    inorder(node.left)
    visit(node)                 # ← "node between"
    inorder(node.right)

postorder(node):
    if node == null: return
    postorder(node.left)
    postorder(node.right)
    visit(node)                 # ← "node last"

The shape is identical across all three; only the position of visit(node) changes. This is why these are sometimes called the “DLR / LDR / LRD” traversals (where D=data/visit, L=left, R=right).

4. Recursive Python

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
def preorder(node, out):
    if not node: return
    out.append(node.val)
    preorder(node.left, out)
    preorder(node.right, out)
 
def inorder(node, out):
    if not node: return
    inorder(node.left, out)
    out.append(node.val)
    inorder(node.right, out)
 
def postorder(node, out):
    if not node: return
    postorder(node.left, out)
    postorder(node.right, out)
    out.append(node.val)

Generator versions are even cleaner:

def inorder_gen(node):
    if node:
        yield from inorder_gen(node.left)
        yield node.val
        yield from inorder_gen(node.right)

5. Iterative Versions (THE Interview Topic)

Recursion is elegant; iteration is what interviewers ask for (“now do it iteratively, with a stack”). Iteration matters when:

  • The tree is deep enough to risk a stack overflow (Python’s default recursion limit is 1000).
  • You need fine control over the traversal (early termination, lazy iteration).

5.1 Iterative Pre-Order (Easiest)

Push nodes onto a stack; pop, visit, push children right-then-left (so left is popped next).

def preorder_iter(root):
    if not root: return []
    out, stack = [], [root]
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.right: stack.append(node.right)   # right first
        if node.left:  stack.append(node.left)    # left last → popped first
    return out

5.2 Iterative In-Order (Medium)

The trick: walk left as deep as possible (pushing onto stack), then visit + go right.

def inorder_iter(root):
    out, stack = [], []
    node = root
    while node or stack:
        while node:                  # walk left
            stack.append(node)
            node = node.left
        node = stack.pop()           # leftmost — visit
        out.append(node.val)
        node = node.right            # then walk into right subtree
    return out

5.3 Iterative Post-Order (Hardest)

Two common approaches:

Approach A: Two-stack trick. Pre-order is “node, left, right”. Reverse pre-order produces “right, left, node”. A trivial change to pre-order — visiting right before left, then reversing the output — gives post-order.

def postorder_iter_two_stack(root):
    if not root: return []
    out, stack = [], [root]
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.left:  stack.append(node.left)
        if node.right: stack.append(node.right)
    return out[::-1]                  # reverse → post-order

Approach B: One stack with a “last visited” pointer. More memory-efficient; tracks whether we’ve already processed the right subtree.

def postorder_iter_one_stack(root):
    out, stack = [], []
    last = None
    node = root
    while node or stack:
        while node:
            stack.append(node)
            node = node.left
        peek = stack[-1]
        if peek.right and last is not peek.right:
            node = peek.right         # explore right
        else:
            out.append(peek.val)
            last = stack.pop()
    return out

Approach A is cleaner and what most interviews accept; Approach B is the “real” iterative post-order.

5.4 Level-Order (BFS)

from collections import deque
 
def levelorder(root):
    if not root: return []
    out, q = [], deque([root])
    while q:
        node = q.popleft()
        out.append(node.val)
        if node.left:  q.append(node.left)
        if node.right: q.append(node.right)
    return out

If you need per-level output (list of lists), capture the size of the queue at the start of each iteration:

def levelorder_grouped(root):
    if not root: return []
    out, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):       # KEY: snapshot size
            node = q.popleft()
            level.append(node.val)
            if node.left:  q.append(node.left)
            if node.right: q.append(node.right)
        out.append(level)
    return out

This level-grouped pattern is constantly asked about in interviews (“zigzag traversal”, “right-side view”, “level averages”, “level-order with depth”).

6. Morris Traversal — O(1) Space (The Trick Algorithm)

Recursion uses O(h) stack space where h is the tree height. Iterative-with-stack also uses O(h). Morris traversal achieves O(1) extra space by temporarily modifying the tree’s pointers: each node’s leftmost descendant in its right subtree (its “in-order predecessor”) gets a temporary pointer back up to the node, providing the “ladder” to climb.

def morris_inorder(root):
    out = []
    cur = root
    while cur:
        if not cur.left:
            out.append(cur.val)
            cur = cur.right
        else:
            # Find in-order predecessor (rightmost in left subtree)
            pred = cur.left
            while pred.right and pred.right is not cur:
                pred = pred.right
            if not pred.right:
                pred.right = cur          # create ladder
                cur = cur.left
            else:
                pred.right = None         # remove ladder
                out.append(cur.val)
                cur = cur.right
    return out

O(n) time, O(1) extra space, but mutates the tree temporarily (restores by end). Rarely required; valuable as “I know one O(1)-space tree traversal.”

7. When to Use Which

OrderUse case
Pre-orderSerialize a tree (with null markers); deep-clone a tree; print directory tree top-down
In-orderOn a Binary Search Tree, yields sorted order — most important property; also: convert BST to sorted list, find k-th smallest in BST
Post-orderDeletions (free children before parent); compute aggregates dependent on subtrees (subtree sums, heights, Tree Diameter); evaluate expression trees
Level-order (BFS)Per-level processing (zigzag, right-side view); shortest path in unweighted tree (already known: just depth); checking “complete tree” property

Specific examples

In-order on BST → sorted. This is the single most-used property of in-order. If you in-order traverse a Binary Search Tree, you visit nodes in strictly increasing order. Many BST algorithms use this implicitly.

Post-order for tree diameter:

def tree_diameter(root):
    diameter = [0]
    def height(node):
        if not node: return 0
        left  = height(node.left)
        right = height(node.right)
        diameter[0] = max(diameter[0], left + right)
        return 1 + max(left, right)
    height(root)
    return diameter[0]

The post-order pattern: compute child results first (height(left), height(right)), then combine for the current node. Used in nearly every “tree DP” problem.

Pre-order for serialization:

def serialize(root):
    out = []
    def go(node):
        if not node:
            out.append("#")
            return
        out.append(str(node.val))
        go(node.left); go(node.right)
    go(root)
    return ",".join(out)

The pre-order with null markers preserves uniqueness — you can deserialize back to the same tree.

8. Construct Tree From Traversals

A common interview question: given two of {pre-order, in-order, post-order}, reconstruct the tree.

  • Pre-order + in-order → unique reconstruction. Pre-order’s first element is root; find it in in-order to split left/right subtrees; recurse.
  • Post-order + in-order → unique reconstruction. Post-order’s last element is root; same idea otherwise.
  • Pre-order + post-order → NOT uniquely determined (multiple trees can produce the same pair). Often needs an extra constraint (e.g., “every node has 0 or 2 children”).
def build_from_pre_in(preorder, inorder):
    inord_idx = {v: i for i, v in enumerate(inorder)}
    self.pre_idx = 0
    def go(lo, hi):                       # in-order range [lo, hi]
        if lo > hi: return None
        root_val = preorder[self.pre_idx]
        self.pre_idx += 1
        node = Node(root_val)
        mid = inord_idx[root_val]
        node.left  = go(lo, mid - 1)
        node.right = go(mid + 1, hi)
        return node
    return go(0, len(inorder) - 1)

9. Complexity

For a tree with n nodes and height h:

TraversalTimeSpace (recursion or queue/stack)
Pre/In/Post-order recursiveO(n)O(h) — recursion stack
Pre/In/Post-order iterative (with stack)O(n)O(h)
Level-order (BFS)O(n)O(w) where w = max width — can be n/2 for a balanced tree’s last level
Morris in-orderO(n)O(1)

Worst-case space

For a balanced tree, h ≈ log₂ n, so recursive traversal is O(log n) space. For a skewed tree (worst case), h = n, so it’s O(n). For BFS, the queue at the widest level can hold up to n/2 nodes (a balanced tree’s bottom level). Never claim “trees take O(log n) space” without specifying balanced.

10. Common Interview Problems by Order

Pre-order

  • LC 144 — Binary Tree Preorder Traversal
  • LC 297 — Serialize/Deserialize Binary Tree
  • LC 100 — Same Tree
  • LC 226 — Invert Binary Tree

In-order

  • LC 94 — Binary Tree Inorder Traversal
  • LC 98 — Validate Binary Search Tree
  • LC 230 — K-th Smallest in BST
  • LC 99 — Recover BST (two nodes swapped)

Post-order

  • LC 145 — Binary Tree Postorder Traversal
  • LC 543 — Diameter of Binary Tree
  • LC 124 — Binary Tree Maximum Path Sum
  • LC 110 — Balanced Binary Tree
  • LC 437 — Path Sum III

Level-order

  • LC 102 — Binary Tree Level Order Traversal
  • LC 107 — Bottom-Up Level Order
  • LC 199 — Right Side View
  • LC 103 — Zigzag Level Order
  • LC 116 — Populating Next Right Pointers

A huge fraction of binary-tree interview problems are “pick the right traversal + add one more thing.” Recognizing the pattern from the prompt is the meta-skill.

11. Pitfalls

11.1 Confusing the Three DFS Orders

The three orders look almost identical in code; one wrong line and you’ve silently produced the wrong traversal. Trace by hand on a small example before accepting your code.

11.2 Stack Overflow on Skewed Trees

A right-skewed tree (every node has only a right child) has height n. Recursive traversal recurses n deep — Python’s default limit (1000) breaks for n > 1000. Use sys.setrecursionlimit(...) or convert to iterative.

11.3 Forgetting Null Markers in Serialization

serialize([1, 2, null, null, 3]) and serialize([1, 2, 3]) would be ambiguous without the null markers. Always emit a placeholder for absent children.

11.4 BFS Without Snapshotting Queue Size

If you need per-level grouping and forget the for _ in range(len(q)) snapshot, you’ll mix nodes from different levels. The snapshot must be captured before you start adding children of the current level.

11.5 Modifying the Tree During Traversal

Generally a bug. Morris traversal does this deliberately and restores — but for any other algorithm, mutating the tree mid-traversal causes chaos. If you need to delete or restructure, do a post-order pass and queue the changes.

11.6 In-Order on a Non-BST Doesn’t Sort

In-order yields the in-order order, which equals sorted order only if the tree is a BST. A general binary tree’s in-order traversal is just whatever order the structure produces.

11.7 Iterative Post-Order Traps

The “two-stack reverse” trick is easy but uses O(n) space (output list itself). The “one-stack with last pointer” trick is more memory-efficient but easy to get wrong. Test on a single-node tree, a left-skewed tree, and a right-skewed tree.

12. Diagram — All Four Orders Side by Side

flowchart TD
  subgraph "Tree"
    R[1] --> L1[2]
    R --> R1[3]
    L1 --> LL1[4]
    L1 --> LR1[5]
    R1 --> RR1[6]
  end

Output sequences for this tree:

  • Pre-order: 1 → 2 → 4 → 5 → 3 → 6
  • In-order: 4 → 2 → 5 → 1 → 3 → 6
  • Post-order: 4 → 5 → 2 → 6 → 3 → 1
  • Level-order: 1 → 2 → 3 → 4 → 5 → 6

What this shows. Same tree, four different visit orders — root’s position is the only difference among the three depth-first orders. Level-order is fundamentally different (uses a queue, BFS-style) rather than a stack/recursion.

13. Open Questions

  • Why isn’t Morris traversal more popular in production? Likely because the “temporary mutation” makes it thread-unsafe and complicates concurrent reads — and the memory savings rarely matter.
  • Are there cleaner ways to teach iterative post-order? Most curricula teach the two-stack reversal trick; some prefer the explicit “last-visited” pointer.

14. See Also

Graph View

Backlinks