Iterative Preorder Traversal: Simulate the Call Stack Without Recursion

The recursive preorder solution is three lines. You write it in your sleep. But in a production codebase with an unbalanced tree of 50,000 nodes, that three-line solution will blow your stack. No error until suddenly there is one. And in an interview, the follow-up is almost always the same: "Can you do it iteratively?"

The answer is yes. Your recursive function already uses a stack. You just can't see it. The iterative preorder traversal makes that stack visible.

This is Part 1 of a three-part series. Part 1 covers preorder. Parts 2 and 3 cover inorder and postorder, where the same trick gets progressively more interesting.

The Order That Defines Preorder

Preorder traversal visits nodes in this sequence: root first, then the left subtree, then the right subtree. Recursively:

visit(node)
traverse(node.left)
traverse(node.right)

For this tree:

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

Preorder produces: 1, 2, 4, 5, 3, 6, 7.

Amber badge = visit order. Node value is inside the circle. The right subtree (node 3) isn't visited until the entire left subtree is done.

You hit 1 (root), then dive left to 2, keep going left to 4, backtrack to 5, then backtrack to 3 and process its subtree. The "backtrack" part is what the call stack handles in the recursive version. In the iterative version, you handle it yourself.

Preorder is the right traversal order whenever you need to process a node before its children. Tree serialization, prefix expression evaluation, copying a tree, recording root-to-leaf paths: all of these need the parent before the children, and preorder gives you exactly that.

The Invisible Stack in Your Recursive Code

Every recursive call pushes a frame onto the call stack. When the function returns, that frame pops. For the tree above, when you call traverse(1), the call stack at its deepest point looks like this:

traverse(1)    ← waiting to recurse right after left finishes
  traverse(2)  ← waiting to recurse right after left finishes
    traverse(4)  ← currently executing, no children

Three frames on the stack for a depth-3 path. The depth of the call stack equals the depth of the current node. This is the O(h) space cost of the recursive version, made concrete.

Same pending work, two different containers. The call stack hides it inside function frames; the explicit stack puts it in a list you can inspect, extend, or throw in a try/except.

Python's default recursion limit is 1000. For a balanced tree, that covers roughly 2^1000 nodes (far more than you'll ever see). For a right-skewed tree where every node has only a right child, height equals the number of nodes. A tree with 1001 such nodes crashes Python's recursive solution with a RecursionError. Calling sys.setrecursionlimit(100000) is a workaround, not a fix. It's also the kind of fix that gets a Jira ticket named after you.

"Maximum call stack size exceeded." r/ProgrammerHumor

The iterative version sidesteps this entirely. Instead of the runtime's call stack, you use a list you control.

If you're familiar with how the DP framework models recursive solutions as decision trees, the call-stack visualization is the same idea: each frame on the stack represents a partially completed subproblem waiting to resume.

The Iterative Preorder Traversal Algorithm

Push root onto a stack. While the stack is not empty: pop a node, visit it, push its right child, push its left child. That's the entire algorithm.

def preorder_traversal(root):
    if not root:
        return []
    result = []
    stack = [root]
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return result

Six lines. No recursion. No risk of hitting the system call stack limit.

Why Push Right Before Left?

This is the detail that trips people up. You push the right child before the left because a stack is LIFO: the left child needs to come out first, so it must go in last.

After popping node 1 and pushing its children, the stack looks like [3, 2] with 2 on top. The next pop gives you 2, which is correct for preorder. If you reversed the push order, the stack would be [2, 3] with 3 on top, and you'd get 1, 3, 6, 7, 2, 4, 5. The program doesn't crash. It silently produces a different traversal.

Get the push order backwards and your output looks plausible enough to pass casual inspection. 1, 3, 6, 7, 2, 4, 5 is not obviously wrong unless you've memorized the expected output. Your tests pass if they're not thorough. You ship it. Someone notices three months later. It's a bug that hides.

Walking Through the Algorithm

Let's trace the full execution on the example tree. Each row is one iteration of the while loop.

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

The stack never holds more than three items for a tree of height 2. One pending right sibling per ancestor level.

The maximum stack depth in this trace is three elements (after step 2). The tree has height 2 (root at depth 0, leaves at depth 2). That bound is not a coincidence.

Complexity: O(n) Time, O(h) Space

Time is O(n) because each node is pushed exactly once and popped exactly once. Two O(1) operations per node, n nodes total. No node is revisited.

Space is O(h) where h is the tree height. This one deserves more than a handwave. At any point during the traversal, what is on the stack? After processing the root and pushing its children, the stack holds the right child (waiting) and the left child (about to be processed). As we descend into the left subtree, we push its right child at each level. By the time we reach a leaf, the stack contains exactly one "pending right sibling" for each ancestor, one entry per level. That is at most h entries.

More formally: at any moment, the stack contains only nodes that are "right children waiting to be visited" for each node on the current root-to-frontier path. There are at most h such nodes in that path, so the stack has at most h elements.

For a balanced binary tree, h = O(log n) and space is O(log n). For a completely skewed tree (a chain of left or right children), h = O(n) and space is O(n). In an interview, state O(h) and then add: "O(log n) for balanced, O(n) worst case." That answer shows you understand the difference.

The recursive solution has identical space complexity since the call stack depth also equals h. The iterative version just makes the accounting explicit and controllable.

One Structure, Every Language

Each snippet uses the standard TreeNode definition from LeetCode: val (or Val in Go), left, and right. The TypeScript snippet defines the class explicitly; the others assume it exists in scope.

from typing import Optional

def preorder_traversal(root: Optional['TreeNode']) -> list[int]:
    if not root:
        return []
    result: list[int] = []
    stack: list['TreeNode'] = [root]
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return result

What Problems Call for Iterative Preorder

Iterative preorder is the right choice when you need DFS on a tree without paying the recursive call stack price, or when an interviewer explicitly asks for the non-recursive version.

The specific problem categories:

Tree serialization. Preorder puts the root value first, then each subtree in sequence. Combined with null markers, the preorder sequence uniquely identifies a tree and can reconstruct it in a single left-to-right scan. Inorder alone cannot (two different trees can share the same inorder sequence without null markers).

Root-to-leaf path collection. You need the root included in every path, and you need to extend the path downward as you go. Preorder visits the parent first, so the path is built incrementally in the right order.

Expression tree prefix conversion. In an expression tree where operators are internal nodes and operands are leaves, preorder produces prefix notation (Polish notation): operator first, then operands. The iterative version is directly usable in a streaming or incremental context where the tree arrives incrementally.

Any tree problem where recursion depth is unbounded. File system directory trees, DOM trees in browser engines, JSON/XML parse trees from user-controlled input: all of these can be arbitrarily deep. The iterative version handles them without a runtime limit.

Recognizing the Pattern

Two signals indicate iterative preorder is the right tool.

Signal 1: process the parent before the children. If your computation at each node depends only on that node and its ancestors (not its descendants), preorder is the right traversal order. The iterative version applies anywhere the recursive version would, with the added benefit of explicit stack control.

Signal 2: "carry state down from parent to child." Preorder traversal naturally propagates information downward. If you notice that each node needs data from its parent (a running sum, a cumulative product, the path taken so far), you can carry that state alongside the node in a tuple on the stack. This is the pattern that makes iterative preorder genuinely more flexible than iterative postorder or inorder.

Worked example 1: Binary Tree Paths (LeetCode 257)

Problem: return all root-to-leaf paths as strings ("1->2->5", "1->3").

Why preorder fits: you need the root in every path, and you build each path by appending nodes as you descend. The direction of information flow is parent to child.

def binary_tree_paths(root):
    if not root:
        return []
    result = []
    stack = [(root, str(root.val))]
    while stack:
        node, path = stack.pop()
        if not node.left and not node.right:
            result.append(path)
        if node.right:
            stack.append((node.right, path + "->" + str(node.right.val)))
        if node.left:
            stack.append((node.left, path + "->" + str(node.left.val)))
    return result

Each stack element is a tuple of (node, path-so-far). The path string grows as you descend. When you hit a leaf, the path is complete. No backtracking, no state restoration, no visited set. The stack naturally handles all of it.

Worked example 2: Path Sum (LeetCode 112)

Problem: does any root-to-leaf path sum to the target?

Why preorder fits: the sum accumulates as you descend. Check at the leaves.

def has_path_sum(root, target_sum):
    if not root:
        return False
    stack = [(root, target_sum - root.val)]
    while stack:
        node, remaining = stack.pop()
        if not node.left and not node.right and remaining == 0:
            return True
        if node.right:
            stack.append((node.right, remaining - node.right.val))
        if node.left:
            stack.append((node.left, remaining - node.left.val))
    return False

Same structure. The tuple carries the remaining sum needed. When you see "carry something down from root to each node," think iterative preorder with a tuple on the stack. This generalizes: swap in a running XOR, a cumulative product, a list of ancestors, whatever the problem needs.

The Quick Recap

• Preorder visits root, then left subtree, then right subtree.
• The iterative version uses an explicit stack in place of the runtime call stack.
• Push right before left. Stack is LIFO. Left must come out first, so left goes in last.
• Time: O(n). Each node is pushed once and popped once.
• Space: O(h). The stack holds at most one pending right sibling per level of depth.
• For balanced trees, O(h) = O(log n). For skewed trees, O(h) = O(n).
• To carry state downward (path, running sum, accumulated value), push tuples of (node, state) instead of bare nodes.
• Use iterative when: recursion depth is unbounded, the interviewer asks explicitly, or you need to carry parent-to-child state without backtracking overhead.
• Parts 2 and 3 cover inorder and postorder, where the push-order trick becomes insufficient and you need a different approach.

If you want to practice this pattern until it's automatic, SpaceComplexity runs voice-based mock interviews on exactly these kinds of problems, with rubric-based feedback on your explanation, not just your code.

One thing that separates strong candidates is the ability to explain why push order matters, not just that it does. Practice narrating the LIFO reasoning out loud. The explanation is half the answer.

Further Reading

• Binary Tree Preorder Traversal (LeetCode 144)
• Tree traversal - Wikipedia
• Tree Traversals (Inorder, Preorder and Postorder) - GeeksforGeeks
• std::stack - cppreference
• ArrayDeque (Java SE 21) - Oracle Docs
• Binary Trees - Stanford CS Education Library