1Understand
The idea
Write a function that solves the problem for one node, assuming it already has the answers for its left and right subtrees. Handle the empty tree as the base case. Almost every tree question (height, sum, balance, mirror) is this shape: recurse into the children and combine.
Intuition
Write a function that solves the problem for one node, assuming it already has the answers for its left and right subtrees. Handle None as the base case. Almost every tree question, height, sum, balance, mirror, is this shape: recurse, then combine.
DFS can be preorder, inorder or postorder depending on when you use the node relative to its children. Returning a value up the call stack is cleaner than mutating globals when the answer is a subtree property.
Watch stack depth on skewed trees: O(n) recursion may need an iterative stack.
What you will be able to do
- Define what dfs returns for a subtree
- Handle the empty tree
When to use it
- Input is a TreeNode root
- Height, size, sum or a property of every subtree
- Compare or mirror trees
2See it
Walkthrough
Post-order height
Tree [1, 2, 3], recurse left/right, then combine at the node.
1 / 4
dfs(1) needs left and right results before combining.
Live template
Line 3 active
Complexity: time O(n), space O(h)
Time O(n), each node once. Space O(h) for the call stack (h = height). Converting to BFS level-order is better when you need per-level aggregates; DFS is the default for path and subtree properties.
Read the walkthrough as text
Maximum depth. Tree 1 with left 2, right 3 with right 4.
depth(None) = 0.depth(2) = 1,depth(4) = 1,depth(3) = 1 + max(0,1) = 2.depth(1) = 1 + max(1, 2) = 3.
In code:
def depth(node):if not node: return 0return 1 + max(depth(node.left), depth(node.right))
Balance checks return height and a boolean together so you still do one traversal.
3Recognise it
Kinds of problems (8)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Pre / in / post-order traversal
Example. Return inorder list of a BST.
How. Recurse left, visit node, recurse right (swap order for pre/post).
Height, size or sum
Example. Maximum depth or subtree sum.
How. Base None → 0; return 1 + max(children) or val + sum(children).
Same / symmetric / subtree checks
Example. Are two trees symmetric?
How. Pair dfs on (left, right) mirroring children each step.
Invert or mirror
Example. Invert a binary tree.
How. Swap children at each node, then recurse on both.
Balanced tree check
Example. Is the tree height-balanced?
How. Return height; if |left−right| > 1, bubble failure; avoid recomputing height per node.
Iterative DFS with a stack
Example. Preorder without recursion.
How. Push root; pop, visit, push right then left for preorder order.
Carry state down the path (max so far)
Example. Path with max value on root-to-leaf routes.
How. Pass running max into children; update global at leaves.
Walk two trees together
Example. Merge two binary trees.
How. Return None if both empty; else combine vals and merge left/right pairs.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
None not handled
Why it happens. Base case forgotten, code reaches `.val` or `.left` on None.
How it fails. Empty tree: dfs(root) immediately does root.val → AttributeError.
Fix. First line: `if not node: return base`.
Subtree results ignored
Why it happens. Recursive calls run but their results never combine.
How it fails. max depth: you call dfs(children) but return 0 always, height is 0 for every tree.
Fix. Use return values: `return 1 + max(left, right)` (or combine per problem).
Recomputed subtrees
Why it happens. A helper recurses the full subtree at every node.
How it fails. balanced check calls height(left) and height(right) that each scan whole subtrees, O(n²).
Fix. Return (height, flag) in one dfs; combine at parent without re-walking.
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.