Traversal and Recursion

A tree problem is two decisions, and this page is both of them. First: which walk - and there are only two, depth-first and level order, because preorder, inorder and postorder are the same depth-first route with the visit line in a different place. Second: which direction the information flows - down from the root, up from the leaves, or both at once.

Get the walk right and you never have to memorise three definitions again. Get the direction right and the code is six lines. Get the direction wrong and you will fight the function for twenty minutes.

1. One walk, three slots

Here is the walk. Every node is arrived at from above, left behind on the way back from its left child, and departed from for the last time after its right child. Three moments, every node, every time:

def walk(node):

if not node:

return

# slot 1: PREORDER - arrived, children untouched

walk(node.left)

# slot 2: INORDER - left subtree finished, right not started

walk(node.right)

# slot 3: POSTORDER - both children finished, about to leave for good

Switch the order buttons below and watch the tree: the pointer's route does not change by a single step. Only the slot that emits does.

Fig. Traversal Explorer

The one depth-first walkCall stack

1

Code

def walk(node):
    if not node: return
    visit(node)        # PREORDER
    walk(node.left)
    visit(node)        # INORDER
    walk(node.right)
    visit(node)        # POSTORDER

Output

1

step 1 / 18

Root before either subtree. The output starts at the root, so preorder is the traversal for copying, serialising, and any "decide top-down" pass.

There is one depth-first walk, and three places to put the visit.

Preorder, inorder and postorder are not three algorithms. They are one algorithm and three choices of when to look at the node. Whenever you cannot remember which is which, do not recall the definition - recall the walk, and ask where the visit line sits relative to the two recursive calls.

2. Preorder: root first

root, left, right. The root is emitted before either subtree exists in the output, which means the first thing you write is always the top of the tree.

def preorder(node, out):

if not node:

return

out.append(node.val) # <- visit, then descend

preorder(node.left, out)

preorder(node.right, out)

Use it when the answer needs to be built top-down, or when the output must be replayable as a construction:

• Copying or cloning a tree - you need the parent before you can attach a child.
• Serialising a tree, because a preorder with null markers uniquely determines the shape (Representation).
• Any "carry information down from the root" pass: path sums, depth, an accumulated prefix, a (lo, hi) range for BST validation. That is section 9.

3. Inorder: root in the middle

left, root, right. It has a name for exactly one reason:

Mnemonic

Inorder on a BST emits sorted order. That is the whole reason the word exists. Everything else about inorder is a consequence: "is this a valid BST" becomes "is this walk increasing", "find the k-th smallest" becomes "stop the walk at the k-th emission", and "turn a BST into a sorted list" is a one-liner.

def inorder(node, out):

if not node:

return

inorder(node.left, out)

out.append(node.val) # <- visit BETWEEN the two calls

inorder(node.right, out)

⚠

Inorder is defined only for binary trees

An n-ary tree has no inorder traversal. "In" means between the left subtree and the right subtree, and a node with three children has two betweens and no principled way to pick one. Preorder, postorder and level order all carry over to n-ary trees unchanged; inorder does not exist there.

4. Postorder: root last

left, right, root. Both children have already been fully processed by the time you reach the node, which makes postorder the traversal for every answer that is assembled from what the children reported.

def height(node):

if not node:

return -1 # empty tree: height -1 in edges

left = height(node.left) # both children report first

right = height(node.right)

return 1 + max(left, right) # <- the node's answer, last

Height, size, diameter, subtree sums, "is this subtree balanced", deleting a tree, evaluating an expression tree - all postorder, all for the same reason. If your recursive function has a return that combines two recursive results, you are writing a postorder traversal whether or not you called it that. Six lines of it are the entire contract in section 8.

5. Iterative depth-first

The recursion uses the call stack. Take it over yourself and you get the same walk with no depth limit - which matters, because Python gives up at around 1000 frames and a degenerate 10000-node tree is a perfectly legal input.

All three walks below share one shape: push (node, False). When a False node is popped, push it back as (node, True) along with whichever children it has - a node is only emitted the second time it comes off the stack, once its True marker pops. The three orders differ only in where the (node, True) push sits relative to the two children pushes.

Preorder pushes (node, True) last, so it's the first thing to pop back off - the node's value comes out before either child is touched.

def preorder_iter(root):

stack, result = [(root, False)] if root else [], []

while stack:

node, visited = stack.pop()

if visited: # 2nd time seeing node: emit

result.append(node.val)

else: # 1st time: re-queue then push children

stack.append((node.right, False)) if node.right else None

stack.append((node.left, False)) if node.left else None

stack.append((node, True)) # pushed LAST -> pops FIRST -> emits before children

return result

Inorder pushes (node, True) between the two children, so the left subtree fully drains before the marker pops, and the right subtree only starts once the marker has already emitted the node.

def inorder_iter(root):

stack, result = [(root, False)] if root else [], []

while stack:

node, visited = stack.pop()

if visited: # 2nd time seeing node: emit

result.append(node.val)

else: # 1st time: re-queue then push children

stack.append((node.right, False)) if node.right else None

stack.append((node, True)) # pushed MIDDLE -> pops after left, before right

stack.append((node.left, False)) if node.left else None

return result

Postorder pushes (node, True) first, so it sits at the bottom of the stack until both children have fully drained above it - no reversal trick needed.

def postorder_iter(root):

stack, result = [(root, False)] if root else [], []

while stack:

node, visited = stack.pop()

if visited: # 2nd time seeing node: emit

result.append(node.val)

else: # 1st time: re-queue then push children

stack.append((node, True)) # pushed FIRST -> pops LAST -> emits after children

stack.append((node.right, False)) if node.right else None

stack.append((node.left, False)) if node.left else None

return result

⚠

Recursive traversal dies on a degenerate tree

Python's default recursion limit is about 1000 frames, and a skewed tree needs one frame per node. A 5000-node tree built from sorted inserts is a legal input that raises RecursionError on the textbook solution. Constraints that say 1 <= n <= 10^4 are telling you this. Either write the iterative form, or raise the limit deliberately - do not discover it on the hidden test.

⚠

Marking the node on pop is not the bug here

Unlike graph BFS, tree traversal has no visited set and needs none - a tree has no second route to any node, so nothing can be reached twice. If you find yourself adding a visited set to a tree traversal, either the input is actually a graph (a "tree" with a cycle in it, which is its own problem class) or you are solving the wrong problem.

6. Level order, and the level fence

Level order is the other walk: a queue, not a stack. It sweeps the tree row by row from the top.

BFS peels the tree one row at a time. The queue holds at most two adjacent levels at any moment, which is why its peak size is the tree's maximum width.

The entire difficulty of level order is one line:

from collections import deque

 

def level_order(root):

if not root:

return []

out, q = [], deque([root])

while q:

size = len(q) # <- THE FENCE. Snapshot, before appending.

level = []

for _ in range(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

⚠

The level fence must be snapshotted before the children go in

for _ in range(len(q)) must read len(q) before any child is appended. Writing while q: with no fence, or re-reading len(q) inside the loop, merges every level into one flat list - and the flat list is still a correct level-order traversal, so the bug only shows up on the problems that need the rows separated. Every "per level" question - averages, largest per row, zigzag, right side view, level sums - is this one line plus two lines of bookkeeping.

Level order is also the answer to a family of questions that never say "BFS":

The question	The level-order form
"average / max / sum of each level"	fold level instead of appending it
"right side view"	take level[-1]
"zigzag"	reverse level on odd rows
"minimum depth"	return the depth of the first leaf you dequeue, and stop - BFS finds it before exploring deeper
"bottom-up level order"	build normally, reverse at the end
"connect each node to its right neighbour"	link level[i] to level[i+1] while draining the row
"maximum width"	carry an index with each node: 2i and 2i+1 for the children, then last - first + 1

Mnemonic

"Level", "depth", "row", "nearest" and "shortest" mean BFS. Depth-first can answer all of those too, but it has to explore the whole tree first; BFS gets minimum depth by stopping at the first leaf. When the question is about distance from the root, the queue is not one option among several - it is the one that lets you quit early.

7. Morris traversal: inorder in O(1) space

Every traversal above costs O(h) extra space for the stack or the queue. Morris traversal does inorder in O(1), by temporarily rewriting the tree.

The idea: before descending into a left subtree, find the rightmost node of that subtree - the node inorder will visit immediately before the current one

• and point its right at the current node. That thread is the return path, so no stack is needed. On the way back, the thread is found again and removed.

def morris_inorder(root):

out, node = [], root

while node:

if not node.left:

out.append(node.val) # no left subtree: emit and go right

node = node.right

else:

pred = node.left # rightmost node of the left subtree

while pred.right and pred.right is not node:

pred = pred.right

if not pred.right:

pred.right = node # thread it: this is the way back

node = node.left

else:

pred.right = None # second visit: unthread and emit

out.append(node.val)

node = node.right

return out

Morris traversal mutates the tree and then puts it back. Mid-run the structure is temporarily not a tree - it has cycles, made of the threads. That is fine for a single-threaded walk that always removes what it added, and it is disqualifying in almost every other situation: it is not thread-safe, it fails on a read-only tree, and an exception mid-walk leaves the tree corrupted. Know it because it is asked, and reach for it only when O(1) space is genuinely required.

8. The recursion contract: two blanks

Everything above is the skeleton. Everything below is what you put in the visit slot - and almost every binary tree problem is one of five shapes.

Start with the one that covers most of them. Every recursive tree function is the same postorder skeleton with two holes in it:

def solve(node):

if not node:

return IDENTITY # blank 1: the answer for an empty tree

left = solve(node.left)

right = solve(node.right)

return COMBINE(left, right, node) # blank 2: how to fold the children in

Filling those two blanks is the entire job. The middle two lines never change.

Problem	IDENTITY	COMBINE
Size (count nodes)	0	1 + left + right
Height in edges	-1	1 + max(left, right)
Height in nodes (LC 104)	0	1 + max(left, right)
Sum of all values	0	node.val + left + right
Maximum value	-inf	max(node.val, left, right)
Count leaves	0	1 if node is a leaf else left + right
Mirror the tree	None	node.left, node.right = right, left; return node

Trust the recursive call.

solve(node.left) returns the finished, correct answer for the left subtree. You do not need to know how, and you must not try to verify it by tracing - that way lies the "hold the whole tree in your head" failure that makes recursion feel hard. Your only job is: given two correct child answers and this node, produce this node's correct answer.

⚠

The base case is None, not a leaf

Write the base case for the empty tree, never for the leaf. if not node.left and not node.right: return 1 looks like it handles the bottom, and it does - right up until a node has exactly one child, at which point the code recurses into None and crashes on .val. if not node: covers the leaf case automatically, because a leaf's two children are both None. One base case, not two.

9. Top-down or bottom-up

The contract in section 8 is the bottom-up shape: information flows from the leaves toward the root, and height() in section 4 is already an instance of it. No accumulator, no nonlocal, no helper, and the function's return value is literally the answer. It is the one to reach for by default.

Top-down is the other direction. The node's own answer is computed on the way in, from what its ancestors already knew, and handed to the children as an argument.

def max_depth_top_down(root):

best = 0

def walk(node, depth):

nonlocal best

if not node:

return

if not node.left and not node.right:

best = max(best, depth) # a leaf knows its own depth

walk(node.left, depth + 1)

walk(node.right, depth + 1)

walk(root, 1)

return best

The tell for top-down: the recursive helper takes extra parameters and usually returns None. Depth, an accumulated path sum, a running prefix, a (lo, hi) range for BST validation, the parent's value - all of these are carried down.

	Top-down	Bottom-up
Traversal	preorder	postorder
Information moves	root → leaves, as an argument	leaves → root, as a return value
Signature	walk(node, context) returning None	solve(node) returning the answer
Needs an accumulator	usually (nonlocal, a list, or self.)	no
Answer for the whole tree lives	in the accumulator after the walk	in the top-level return
Natural fit	paths, depths, ranges, anything about ancestors	sizes, heights, sums, anything about descendants
Examples	path sum (112), BST validate (98), root-to-leaf numbers (129)	height (104), diameter (543), balanced (110), subtree sums (508)

Mnemonic

Ancestors go down, descendants come up. If the node's answer depends on where it is in the tree, pass that down as a parameter. If it depends on what is below it, return it up. If it depends on both, you want section 10.

10. The two-answers pattern

Some problems need a node to return one thing to its parent while a different thing is being accumulated globally. Diameter is the canonical case, and it is worth understanding precisely, because the same shape solves a dozen problems.

The longest path through the tree need not pass through the root. It could sit entirely inside a subtree. So the recursion cannot simply return "the longest path below me" - its parent cannot use that number for anything.

def diameter(root):

best = 0

def height(node):

nonlocal best

if not node:

return -1 # empty subtree: height -1 in edges

l = height(node.left)

r = height(node.right)

best = max(best, l + r + 2) # the path THROUGH node: recorded

return 1 + max(l, r) # the height: RETURNED

height(root)

return best

Two different quantities, computed in the same pass:

• Returned upward - the value the parent can extend. It must be a single downward path, because a parent can only attach to one of them.
• Recorded globally - the value that is complete here and can never be extended. A path that bends at this node has used up its one turn.

Return what the parent can use; record what is already finished.

Whenever a problem's answer "does not have to pass through the root", this is the pattern. Diameter (543), maximum path sum (124), longest univalue path (687), longest consecutive sequence (298), and "is this balanced" (110, where the recorded value is a boolean) are all the same six lines with a different best update.

⚠

Returning the global answer instead of the extendable one

The bug is returning best, or returning l + r + 2, from the helper. It type-checks, it passes the tests where the answer does go through the root, and it is wrong the moment the longest path bends in a subtree - because the parent then adds 1 to a number that already used both directions. If the helper's return value is used by the parent with a 1 + max(...), it must be a height, full stop.

11. Paths, and the one backtracking rule

Root-to-leaf path problems carry a list down and need it to shrink again on the way back out.

def all_paths(root):

out, path = [], []

def walk(node):

if not node:

return

path.append(node.val) # choose

if not node.left and not node.right:

out.append(list(path)) # COPY, not `path`

walk(node.left)

walk(node.right)

path.pop() # un-choose: the backtrack

walk(root)

return out

Three lines, three ways to get it wrong:

⚠

Append the list, not a copy, and every answer is the same list

out.append(path) stores a reference. The very next path.pop() mutates the object you just stored, and by the end out is a list of n identical empty lists. It must be list(path) or path[:] or path.copy(). The symptom is unmistakable once you have seen it: the right number of answers, all wrong, all identical.

⚠

The pop() must be unconditional

Every append needs exactly one matching pop, on every exit path from the function. An early return that skips the pop leaves the node on the path forever and corrupts every subsequent branch. The safe shape is the one above: append at the top, pop at the bottom, and never return in between. If a branch must exit early, pop first.

The alternative that avoids backtracking entirely: pass an immutable value down. walk(node.left, path + [node.val]) needs no pop at all, because each call gets its own list. It costs O(n) per call instead of O(1), which turns an O(n) walk into O(n * h) - fine for a small tree, and the reason the mutable-plus-backtrack version is the standard.

12. Two trees at once

When a problem compares two trees, recurse on both in lockstep, and handle the three null cases before touching a value.

def is_same(p, q):

if not p and not q:

return True # both empty: equal

if not p or not q:

return False # exactly one empty: not equal

return (p.val == q.val

and is_same(p.left, q.left)

and is_same(p.right, q.right))

Symmetry (LeetCode 101) is the same function with the recursion crossed: compare left.left against right.right, and left.right against right.left. That single change is the whole problem, and it is why "same tree" and "symmetric tree" are one function with a mirrored call.

⚠

Checking p.val == q.val before the null cases

Both-null, one-null, neither-null - in that order, every time. Testing values first dereferences a None on the first lopsided pair. Testing if p and q first quietly reports two empty trees as unequal. The three-case ladder above is not verbosity; each rung catches a real input.

13. When you need a helper

The top-level signature is fixed by the problem. Add an inner helper whenever the recursion needs something the signature does not give it:

You need	Helper signature	Example
Depth or an accumulated value from above	walk(node, depth)	LC 129, sum root-to-leaf numbers
A bound inherited from ancestors	walk(node, lo, hi)	LC 98, validate BST
To return two things at once	walk(node) -> (height, ok)	LC 110, balanced binary tree
To record a global while returning something else	nonlocal best inside walk(node)	LC 543, diameter
A path being built and unwound	walk(node) closing over path	LC 257, binary tree paths

⚠

nonlocal is required to rebind, and a mutable container avoids it

Assigning to a name anywhere in a function makes that name local for the whole function body, so best = max(best, x) inside the helper raises UnboundLocalError without a nonlocal best. Two ways out: declare nonlocal best, or make best a one-element list and mutate it (best[0] = ...), which needs no declaration because you are not rebinding the name. The nonlocal version is clearer; the list version is what you will see in a lot of published solutions.

14. Complexity, and the two accidental quadratics

Every traversal on this page visits each node exactly once, so all of them are O(n) time. They differ only in space: depth-first costs O(h) for the stack, which is O(log n) on a balanced tree and O(n) on a degenerate one; level order costs O(w) for the queue, where w is the maximum width, which is O(n) on a balanced tree (the bottom row alone is half the nodes) and O(1) on a degenerate one. The two are worst-case opposites.

There are then two ways to lose the O(n) without noticing, and both look linear.

Recomputing a value the recursion already had. The naive balanced-tree check calls height() at every node, and height() itself walks the whole subtree - so the work is O(n) per node, O(n^2) overall. The fix is always the same: compute the value once, bottom-up, and return it along with the answer, as in section 10.

Concatenating results at every node. return left_list + [node.val] + right_list builds a new list at every node, so an inorder traversal written that way is O(n^2) on a skewed tree instead of O(n). Append to one shared list instead.

Shape	Time	Space	Note
Plain recursive traversal	O(n)	O(h) call stack	O(log n) balanced, O(n) skewed
Iterative traversal	O(n)	O(h) explicit stack	same walk, no recursion limit
Level order	O(n)	O(w) queue	w is the max width; O(n) on a balanced tree
Morris traversal	O(n)	O(1)	mutates the tree mid-walk
Two-answers pattern	O(n)	O(h)	same walk, one extra variable
Recompute height at every node	O(n^2)	O(h)	the classic accidental quadratic
Path building with path + [x]	O(n * h)	O(n * h) output	immutable copies at every level
Path building with append/pop	O(n) plus output	O(h)	the standard

O(n log n) is the wrong guess for "recompute height at every node". The log n assumes a balanced tree, and complexity is a worst case. On a skewed tree, the node at depth d has a subtree of size n - d, and summing that over all depths gives n^2 / 2. Whenever you catch yourself reaching for n log n on a tree, check whether the log is a guaranteed height or just a hopeful one.

15. Which shape, in one question

Read the problem statement, not the tree. The first column is what the question says; the rest is both decisions at once - the walk, and the direction.

The problem says	Walk	Direction	Because
"sorted", "k-th smallest", "validate BST"	inorder	top-down (lo, hi) for validation	inorder on a BST is sorted order
"height", "depth of the tree", "diameter", "balanced"	postorder	bottom-up	the node needs both children's answers
"the longest path", and it need not pass the root	postorder	bottom-up, two answers (section 10)	return a height, record a best
"path from the root", "root-to-leaf", "sum along the way"	preorder	top-down, with backtracking	the answer accumulates downward
"serialise", "clone", "copy"	preorder	top-down	the parent must exist before the child attaches
"level", "row", "each depth", "side view", "zigzag"	level order	row by row	the rows are the answer
"minimum depth", "nearest leaf", "fewest steps"	level order	row by row, stop early	BFS can stop at the first hit; DFS cannot
"same tree", "symmetric", "subtree of another"	any, in lockstep	two trees at once (section 12)	the three null cases come first
"count nodes matching X", order irrelevant	any - use preorder	bottom-up	no ordering constraint, so pick the shortest to write

Where to go next

• Structural Approach to Tree Concepts
  • nine specific traps in tree recursion, each worked through end to end.
• Binary Search Trees - where inorder stops being one option and becomes the point, and the top-down (lo, hi) pattern in its natural home.
• Traversal practice and post-order processing practice
  • the problem sets for this page.