dsa.university
start_free
Blog/FUNDAMENTALS

Recursion to iteration, without breaking the base case

Raising the recursion limit works right up until it segfaults. A mechanical procedure for converting any recursive function to an explicit stack, including the post-order case people get wrong.

KT
Kenji TanakaProblem setting
31 July 2026·7 min read

A recursive solution that works on every sample and dies on the large test is one of the most common failure modes in the trees and graphs tracks. The tree is a degenerate left spine of 10^5 nodes, the recursion goes 10^5 frames deep, and the runtime gives up.

Why raising the limit is not the fix

In CPython, sys.setrecursionlimit raises the interpreter's own counter but does nothing about the actual C stack underneath it. Raise it far enough and the program stops raising a clean RecursionError and starts segfaulting instead — you have traded a catchable error for a crash. It is a workaround with a cliff in it.

Do not ship this

sys.setrecursionlimit(300000) is the algorithmic equivalent of taping over a warning light.

Pre-order converts trivially

If all the work happens on the way down, the conversion is mechanical: push the root, pop, process, push children. Push the right child first so the left is processed first.

python
1def preorder(root):
2 out, stack = [], [root] if root else []
3 while stack:
4 node = stack.pop()
5 out.append(node.val)
6 if node.right:
7 stack.append(node.right)
8 if node.left:
9 stack.append(node.left)
10 return out

Post-order is where people slip

Post-order needs each node visited twice: once to schedule its children, once to combine their results. The clean way to express that is to push a marker alongside the node saying which visit this is.

python
1def postorder(root):
2 out, stack = [], [(root, False)] if root else []
3 while stack:
4 node, expanded = stack.pop()
5 if expanded:
6 out.append(node.val) # both children already done
7 continue
8 stack.append((node, True)) # schedule the combine
9 if node.right:
10 stack.append((node.right, False))
11 if node.left:
12 stack.append((node.left, False))
13 return out

That two-state marker is exactly the return address a real stack frame carries. You are not inventing a trick; you are writing down by hand what the language was doing for you.

Carrying return values

When the recursion returns a value rather than appending to a list, keep a dictionary from node to computed result, filled in on the combine visit. The parent reads its children out of that dictionary because, by the time a parent is expanded, both children have already been written.

python
1def depth(root):
2 if not root:
3 return 0
4 res, stack = {None: 0}, [(root, False)]
5 while stack:
6 node, expanded = stack.pop()
7 if expanded:
8 res[node] = 1 + max(res[node.left], res[node.right])
9 continue
10 stack.append((node, True))
11 for child in (node.left, node.right):
12 if child:
13 stack.append((child, False))
14 return res[root]

When not to bother

If the depth is provably logarithmic — a balanced tree, a divide-and-conquer split — recursion is fine and clearer. Convert when the depth can be linear in the input: linked lists, unbalanced trees, path-shaped graphs, and any DFS on a general graph where the input could be a long chain.

recursionstackpython
Practise this

Reading about a pattern is not the same as producing it under time pressure. The problems that drill this are in the curriculum, in order.

open_curriculumcreate_account
previousWhen hashing stops being O(1)next The eight dynamic programming recurrences that cover most interviews

Related reading.

TREES

Why your BST validation passes the samples and dies on depth

7 min readFUNDAMENTALS

Reading a call stack without a debugger

7 min readFUNDAMENTALS

When hashing stops being O(1)

6 min read