Trees

Tree DFS

Recursive depth-first traversal that combines results from subtrees.

Easy, about 60 minutes to practise.

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

i
1
2
3
012
i → index 0

dfs(1) needs left and right results before combining.

left, right = dfs(node.left), dfs(node.right)

Live template

Line 3 active

1def dfs(node):
2 if not node: return base
3 left, right = dfs(node.left), dfs(node.right)
4 return combine(node.val, left, right)

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.

  1. depth(None) = 0.
  2. depth(2) = 1, depth(4) = 1, depth(3) = 1 + max(0,1) = 2.
  3. depth(1) = 1 + max(1, 2) = 3.

In code:

  • def depth(node):
  • if not node: return 0
  • return 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.

All lessons