Skip to content

Trees & Recursion

This part exists because tree recursion looks like magic until it suddenly doesn't. The usual sticking point is a four-line function like this one:

def height(node):
    if node is None:
        return -1
    return 1 + max(height(node.left), height(node.right))

You read it, it looks too short to be correct, you try to trace it in your head, you lose track three calls deep, and you're left thinking "I guess it works?"

These chapters fix that in order:

  1. Thinking recursively about trees: the mental model. Stop tracing; start trusting. The three questions.
  2. Tree height, slowly: apply the model to height, derive every piece (including that strange -1), then watch the call stack in slow motion.
  3. Depth vs height: the other common mix-up. Why depth flows down the tree and height flows up.
  4. One template, many problems: the same three-question template solves a whole family of problems, and there's one trap to watch for.
  5. Practice: problems to lock it in.

If you only have ten minutes

Read the three questions in chapter 1, then play with the height visualizer on the Linked list preset and the Full preset. Watch the call stack panel.