Convert Recursion to Iteration With an Explicit Stack

Every recursive function runs on a stack you never see. Each call pushes a frame holding its arguments, its local variables and the line to return to; each return pops one. Converting recursion to iteration means making that stack an ordinary list you manage yourself. It sounds like a party trick until a tree turns out to be 100,000 levels deep, or an interviewer asks for an iterator that returns one value at a time. Then it is the only answer.

The problem it solves

A recursive solution is often the clearest one, and it has three limits:

• Depth. CPython's default recursion limit is 1,000 frames, as of September 2026, and the real stack is small in most languages. A degenerate tree or a long linked structure breaks it.
• No pausing. A recursive walk runs to completion. You cannot return the third value, go away, and ask for the fourth later without keeping the frames alive somewhere.
• Hidden cost. Each frame carries interpreter overhead that an explicit list of small tuples does not.

When the recursive call is the last thing a function does, a tail call, a loop with an accumulator replaces it. When work remains after the call, something has to remember where to come back to. That something is your own stack.

The intuition

Ask what a frame would hold, then store exactly that:

• Pending work only. In the lesson's inorder walk, a frame is waiting to print its node after its left subtree is done. So the stack holds nodes whose visit is owed. Dive left pushing every node you pass; when the left runs out, pop, report, and turn right.
• A resume point when there is work after the calls. A recursive height function computes both children, then returns 1 + max(left, right). The explicit version pushes (node, phase): in phase 0 it schedules itself for phase 1 and pushes both children; in phase 1 the children's results are ready on a second stack, and it combines them. The phase is the "line to return to" that the runtime would have stored.
• Order is reversed. A stack pops last-in first. To run the left child first, push it last.

The same stack, kept between calls, becomes an iterator: each next() does one pop and one left descent, and stops. That is how a "BST iterator" runs in O(h) memory and amortised O(1) per value.

Watch it run

The animation walks the lesson's five-node tree. It opens with the reason the stack exists: this is no tail call, work remains after the recursive call, so something has to remember the way back. Push 4 and keep going left; its own visit is owed, not done. Push 2, then push 1: nothing further left, so this is where the output begins. Pop 1 and print it; it has no right child, so the next answer is already on the stack. Pop 2, print it, then turn right and repeat the whole descent: push 3, pop 3. Pop 4, turn right, push 5. Pop 5 and print it: no right child and an empty stack, so the walk is over. The output reads 1, 2, 3, 4, 5, the same order the recursion gives, with the stack on the heap and no depth limit beyond memory.

The code

The lesson's inorder walk, and height with a phase flag and a results stack for the work after both calls:

class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def inorder(root):
    """The lesson's walk: the stack holds every node whose visit is still owed."""
    out, stack, n = [], [], root
    while stack or n:
        while n:                          # dive left, noting the way back
            stack.append(n)
            n = n.left
        n = stack.pop()                   # nothing further left: this node is next
        out.append(n.val)
        n = n.right                       # then the same descent on its right
    return out

tree = Node(4, Node(2, Node(1), Node(3)), Node(5))
print(inorder(tree))                      # [1, 2, 3, 4, 5]

def height_rec(n):
    return 0 if n is None else 1 + max(height_rec(n.left), height_rec(n.right))

def height(root):
    """Work AFTER both calls: each frame is (node, phase), and results go on a second stack."""
    frames, results = [(root, 0)], []
    while frames:
        n, phase = frames.pop()
        if n is None:
            results.append(0)             # base case: return 0
        elif phase == 0:
            frames.append((n, 1))         # come back here after both children
            frames.append((n.right, 0))   # pushed first, so it runs second
            frames.append((n.left, 0))
        else:
            right, left = results.pop(), results.pop()
            results.append(1 + max(left, right))   # the line after the recursive calls
    return results.pop()

print(height_rec(tree), height(tree))     # 3 3

The same stack kept between calls is a pausable iterator. After two values it holds exactly the two visits still owed:

class InorderIterator:
    """The same stack, paused between values: each next() does one pop and one descent."""
    def __init__(self, root):
        self.stack = []
        self._dive(root)
    def _dive(self, n):
        while n:
            self.stack.append(n)
            n = n.left
    def has_next(self):
        return bool(self.stack)
    def next(self):
        n = self.stack.pop()
        self._dive(n.right)
        return n.val

it = InorderIterator(tree)
print(it.next(), it.next(), len(it.stack))   # 1 2 2  -> stopped early, two visits still owed

Why it matters: a chain 100,000 levels deep breaks the recursive walk and is routine for the explicit one:

import sys

deep = None
for v in range(100_000):                  # a left-leaning chain, 100,000 levels deep
    deep = Node(v, deep)

def inorder_rec(n, out):
    if n:
        inorder_rec(n.left, out)
        out.append(n.val)
        inorder_rec(n.right, out)
    return out

try:
    inorder_rec(deep, [])
except RecursionError:
    print("RecursionError at limit", sys.getrecursionlimit())   # RecursionError at limit 1000
print(len(inorder(deep)), height(deep))   # 100000 100000

Checked on 500 seeded random trees of up to 40 nodes against the recursive originals: the iterative inorder, the phase-flag height and the iterator drained to the end must all agree:

import random

def random_tree(size):
    if size == 0:
        return None
    left = random.randint(0, size - 1)
    return Node(random.randint(0, 99), random_tree(left), random_tree(size - 1 - left))

random.seed(29)
ok = True
for _ in range(500):
    t = random_tree(random.randint(0, 40))
    want = inorder_rec(t, [])             # brute force: the recursive originals
    ok &= inorder(t) == want and height(t) == height_rec(t)
    it, got = InorderIterator(t), []
    while it.has_next():
        got.append(it.next())
    ok &= got == want
print(ok)                                 # True

The complexity

• Time: unchanged, O(n) for a walk over n nodes. Each node is pushed and popped once; the height version twice, once per phase.
• Space: O(h) for height h, the same as the recursion, but on the heap. A 100,000-entry list is ordinary; a 100,000-frame call stack is not.
• Iterator: O(h) memory and amortised O(1) per next(), since every node is pushed and popped exactly once over the whole walk.

Where it goes wrong

• Pushing children in the wrong order. Push the right child first if the left must run first.
• Losing the work after the call. A single stack of nodes cannot compute a height; the combine step needs a phase flag, or a visited marker, and somewhere to keep the children's results.
• Marking visited too early in graphs. For a DFS on a graph, check seen when popping, as in DFS vs BFS.
• Raising the recursion limit instead. sys.setrecursionlimit moves the failure from an exception to a possible interpreter crash when the real stack runs out.

When it shows up in interviews

As "do it without recursion" after any tree answer, as "implement a BST iterator with next() and has_next()", and as the recovery when a recursive DFS meets a very deep input. The iterative preorder and postorder variants are in binary tree traversal, the accumulator rewrite for tail calls is in tail recursion, and the Big-O cheat sheet notes where recursive DFS can hit the limit.

How to say it in an interview

"The recursion is using the call stack as its data structure, so I'll make that stack explicit. For inorder I push nodes while going left, pop one, report it and move to its right child; the stack holds exactly the visits still owed. If there's work after the recursive calls, like combining children's heights, I push the node with a phase flag so it comes back after its children, and keep results on a second stack. Time is still O(n) and space O(h), but on the heap, so depth is no longer a limit, and keeping the stack between calls gives me an iterator."