Trees: Traversals and Core Patterns
Picture a company org chart: a CEO at the top, managers below, workers below them. That shape, one node with children, children with their own children, is a tree. Most tree problems have a simple trick: the answer for a node is built from the answers of its children. Write a function that trusts its own recursive calls, and the tree problem nearly solves itself.
Visiting every node in a tree
Take this small tree of numbers:
5
/ \
3 8
/ \ \
1 4 9There are four common ways to walk through it, and they differ only in when you record a node compared to its children.
- Preorder (node, left, right): record the node first, then its subtrees.
5, 3, 1, 4, 8, 9. Good for copying or serializing a tree, since you write the parent before you write its children. - Inorder (left, node, right): record the node between its subtrees.
1, 3, 4, 5, 8, 9. For a search tree (covered in the next lesson), this always comes out sorted. - Postorder (left, right, node): record the node last.
1, 4, 3, 9, 8, 5. Use this whenever children must be fully handled before the parent, such as deleting a tree from the bottom up, or totaling up a subtree's values. - Level order: visit row by row, left to right:
[5], [3, 8], [1, 4, 9]. This one isn't recursive at all; it uses a queue, the same tool BFS uses on graphs later in this course.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def preorder(root):
if root is None:
return []
return [root.val] + preorder(root.left) + preorder(root.right)
def inorder(root):
if root is None:
return []
return inorder(root.left) + [root.val] + inorder(root.right)
def postorder(root):
if root is None:
return []
return postorder(root.left) + postorder(root.right) + [root.val]
from collections import deque
def level_order(root):
if root is None:
return []
result = []
queue = deque([root])
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return resultThe versions above build small lists and glue them together with +. That reads well, but real code usually passes one shared list down through the recursion instead, so it doesn't keep building and throwing away little lists. Know both; be ready to write the faster one if asked.
Remember: preorder writes the parent first, postorder writes it last, inorder puts it in the middle. Level order is the odd one out: no recursion, just a queue.
Doing it without recursion
Every recursive traversal above has an iterative version that uses an explicit stack instead of the call stack. Interviewers ask for this to check that you understand what the recursion was actually doing, not that you memorized three lines.
Preorder is the easiest to convert: push right before left, so left comes off the stack first.
def preorder_iterative(root):
if root is None:
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 resultInorder is trickier, since you can't just push both children at once. You have to walk all the way left first, process the node you land on, then step right:
def inorder_iterative(root):
result = []
stack = []
node = root
while stack or node:
while node: # go as far left as possible
stack.append(node)
node = node.left
node = stack.pop() # process the node
result.append(node.val)
node = node.right # then explore the right subtree
return resultPostorder iteratively is the fiddly one. Do a "node, right, left" walk (swap the push order from preorder above), then reverse the result. That flips it into "left, right, node" for free.
def postorder_iterative(root):
if root is None:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return result[::-1]Remember: preorder-iterative pushes right then left. Postorder-iterative is preorder's "node, right, left" twin, reversed at the end. Inorder needs a "walk left, then pop" loop.
Two facts about a tree's shape
Two properties come up again and again, so get them cold.
Height: how many edges are on the longest path from a node down to a leaf. A single node has height 0. Height is naturally computed bottom-up, a postorder-shaped recursion: a node's height is 1 more than the taller of its two children's heights.
Balance: a tree is height-balanced if, at every node, the heights of its left and right subtrees differ by at most 1. Checking this the naive way, calling a height function at every node, costs O(n²) in the worst case on a long, skewed tree, since you recompute overlapping heights over and over. The fast version computes height and checks balance in the same single postorder pass, O(n) total.
Remember: compute height bottom-up. Check balance in the same pass as computing height, don't call a separate height function per node.
Invert Binary Tree
Invert Binary Tree (LeetCode 226)
Flip a photo of the tree left to right: every left child becomes a right child and vice versa, all the way down. That is the whole problem. It is a postorder-shaped recursion: invert both subtrees, then swap them onto the node.
Approach: Base case: None inverts to None. Recursive case: swap root.left and root.right, after first inverting each of them.
def invert_tree(root):
if root is None:
return None
root.left, root.right = invert_tree(root.right), invert_tree(root.left)
return rootComplexity: Time O(n), visits every node once. Space O(h) for the recursion stack, where h is the tree's height (O(log n) if balanced, O(n) if it's a long chain).
Common mistakes:
- Swapping
root.left/root.rightbefore recursing on the original children. That inverts the wrong subtree. The simultaneous-assignment version above sidesteps this by finishing both recursive calls before either assignment happens. - Forgetting the
Nonebase case, which causes infinite recursion.
Remember: invert the children first, then swap them onto the parent, not the other way around.
Maximum Depth of Binary Tree
Maximum Depth of Binary Tree (LeetCode 104)
The depth of a tree is 1 (for the current node) plus whichever of its two subtrees goes deeper. That's the entire recursion, a textbook postorder shape.
Approach: Base case: an empty tree has depth 0. Recursive case: 1 + max(depth(left), depth(right)).
def max_depth(root) -> int:
if root is None:
return 0
return 1 + max(max_depth(root.left), max_depth(root.right))Complexity: Time O(n), space O(h) for the recursion stack.
Common mistakes:
- Off-by-one: forgetting the
+ 1for the current node, or adding it twice. - Writing an iterative BFS version without correctly counting levels; you need to count levels, not nodes.
Remember: depth is 1 plus the deeper child's depth. An empty tree has depth 0.
Same Tree
Two trees match if their roots hold the same value and both pairs of subtrees also match. That's a direct structural recursion comparing two trees side by side, step by step.
Approach: Base cases: both None means equal; exactly one None means not equal. Recursive case: values match AND left subtrees match AND right subtrees match.
def is_same_tree(p, q) -> bool:
if p is None and q is None:
return True
if p is None or q is None:
return False
return (
p.val == q.val
and is_same_tree(p.left, q.left)
and is_same_tree(p.right, q.right)
)Complexity: Time O(min(n, m)), stops the instant the trees diverge. Space O(min(h_p, h_q)) recursion stack.
Common mistakes:
- Reading
p.valbefore checking whetherpisNone. That crashes with an attribute error onNone.
Remember: check both-None and either-None first. Only then compare values and recurse into both children.
Binary Tree Level Order Traversal
Binary Tree Level Order Traversal (LeetCode 102)
"Group nodes by their depth" is exactly what BFS gives you for free, as long as you process the queue one full level at a time instead of one node at a time.
Approach: Use a queue. At each step, note the current queue length; that number is exactly how many nodes belong to the current level. Pop that many, collect their values, and enqueue their children for the next round.
from collections import deque
def level_order_traversal(root):
if root is None:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
level_values = []
for _ in range(level_size):
node = queue.popleft()
level_values.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level_values)
return resultComplexity: Time O(n), every node is enqueued and dequeued exactly once. Space O(w) for the queue, where w is the widest level, plus O(n) for the output.
Common mistakes:
- Not snapshotting the queue's length before the inner loop. Checking the live length inside the loop lets it grow as you enqueue children, which merges levels together.
- Using
list.pop(0)(O(n) per call) instead ofdeque.popleft()(O(1)), or using a stack where a queue is needed.
Remember: snapshot the queue length before draining it. That number is exactly one level's worth of nodes.
Naming the shape before you code
Every problem in this lesson reduces to one of three shapes: does a node's answer depend only on its children's answers (postorder: Invert, Max Depth)? Does it depend on walking two trees in lockstep (Same Tree)? Or does it need to go level by level (Level Order)? Spend ten seconds naming which shape a new tree problem fits before writing any code. Guessing at the recursion instead of naming the shape first is where most tree bugs start.
Remember: name the shape (postorder, lockstep comparison, or level-by-level) before you write a single line.