Lesson 29 — Trees II: Trust the Recursion

~20 minutes · Day 32 · tree recursion · Python

Tonight's problem is Maximum Depth of Binary Tree. Interviewers like it because it reveals whether you can stop trying to control the whole tree at once. A tree problem usually becomes smaller the moment you ask, “what answer should the left child give me, and what answer should the right child give me?”

The invariant

The answer for a node is a function of its children's answers; trust the recursion on subtrees and only decide what happens at this node.

That's the whole move. A binary tree node has up to two children. For height, the left child can answer, “my subtree is this tall,” and the right child can answer the same. The current node only chooses the larger answer and adds itself.

The root does not solve the whole tree; it waits for left and right heights, then adds itself.

Maximum Depth: the noisy way first

The slow instinct is to collect every root-to-leaf path, keep copying the current path, and then take the longest one. That works, but the path copies can cost O(nh): n nodes, and path length up to height h. The problem is not asking for the paths. It only wants one number.

So return one number from each subtree. On LeetCode's version, an empty child has depth 0; a real node has depth 1 + max(left_depth, right_depth).

class Solution:
    def maxDepth(self, root):
        if root is None:
            return 0                         # empty subtree: height 0
        left = self.maxDepth(root.left)      # trust left subtree
        right = self.maxDepth(root.right)    # trust right subtree
        return 1 + max(left, right)          # decide at this node

Do not step through every recursive call at once. Step through one node. If both children hand you correct heights, the only decision left is 1 + max(left, right).

Transfer: same question, new costume

Suppose the question changed to: return the total number of nodes in a binary tree. Same pattern. Before opening the answer, predict the return value for an empty subtree and the formula for a real node.

def count_nodes(root):
    if root is None:
        return 0
    left = count_nodes(root.left)
    right = count_nodes(root.right)
    return 1 + left + right

What the trade buys you

The space in the recursive version is the call stack: one active call per level of height.

Practice — answer before you scroll past

def maxDepth(root):
    if root is None:
        return 0
    left = maxDepth(root.left)
    right = maxDepth(root.right)
    return max(left, right)

Your move (tonight)

Solve Maximum Depth of Binary Tree in your Notion tracker with the cycle — predict → attempt → compare → encode. In the predict step, say the invariant out loud. In the attempt step, write the base case before the recursive calls. In the encode step, write the one-line rule that made the recursion work.