Computing Tree Height via Recursion

Welcome back! In our last few lessons, we focused on different ways to traverse a binary tree, visiting every node using either depth-first or breadth-first strategies. We learned how to generate ordered lists of nodes, whether by diving deep into branches or exploring level by level.

Today, we shift from simply visiting nodes to using traversal to compute properties of the tree itself. This lesson will show you a powerful and widely applicable recursive pattern: solving a problem for a tree by first solving it for its smaller subtrees and then combining those results. We'll focus on calculating a tree's height, a fundamental property that appears in many more complex problems. This approach is a cornerstone of thinking algorithmically about recursive data structures like trees.

The Universal Recursive Pattern for Trees

Many binary tree problems can be solved with a simple, elegant recursive strategy. Since every subtree of a tree is itself a smaller tree, we can often define a function that calls itself on its children.

The short video from the "Inside code" channel provides a superb high-level overview of this very idea. It's a mental model you'll use again and again.

As the video explains, the pattern is:

1. Define one or more base cases. What should happen on the simplest possible input (e.g., an empty tree)?
2. Call the function recursively on the left subtree. Assume it magically gives you the correct answer for that smaller tree.
3. Call the function recursively on the right subtree. Again, assume you get the right answer for that part.
4. Combine the results. Use the answers from the left and right subtrees, plus information from the current node, to calculate the answer for the tree rooted at the current node.

This process, where work is done after the recursive calls return, is a form of post-order traversal. We go all the way down to the leaves and then "bubble up" the answers.

Calculating the Maximum Depth of a Tree

Let's apply this pattern to a classic problem: finding the maximum depth (or height) of a binary tree. The depth is defined as the number of nodes along the longest path from the root down to the farthest leaf node.

Let's frame this using our four-step pattern:

1. Base Case: If a tree is empty (root is null), its depth is 0. There are no nodes.
2. Recursive Call (Left): Find the maximum depth of the left subtree: leftDepth = maxDepth(root.left).
3. Recursive Call (Right): Find the maximum depth of the right subtree: rightDepth = maxDepth(root.right).
4. Combine Results: The longest path through the current node must go through either the deepest part of the left subtree or the deepest part of the right subtree. So, we take the maximum of their depths. We then add 1 to account for the current node itself. The result is 1 + Math.max(leftDepth, rightDepth).

The following resource from Algo.monster provides an excellent, detailed explanation of this logic, complete with a helpful analogy.

To see this "bubbling up" of results in action, the next video offers a fantastic visualization of the recursive calls and return values.

Here is the complete TypeScript implementation for your reference:

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;

    constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function maxDepth(root: TreeNode | null): number {
    // 1. Base Case: An empty tree has a depth of 0.
    if (root === null) {
        return 0;
    }

    // 2. & 3. Recursive Calls: Get the depth of left and right subtrees.
    const leftDepth = maxDepth(root.left);
    const rightDepth = maxDepth(root.right);

    // 4. Combine Results: The depth is 1 (for the current node) plus the greater of the two subtree depths.
    return 1 + Math.max(leftDepth, rightDepth);
}

This algorithm has a time complexity of $O(N)$ because it visits every node exactly once. The space complexity is $O(H)$, where $H$ is the height of the tree, due to the space used by the recursion call stack.

A Subtle Variation: Minimum Depth

Now, let's consider a related problem: find the minimum depth of a binary tree. This is the number of nodes along the shortest path from the root to a leaf.

Your first thought might be to simply change Math.max to Math.min. Let's test that intuition.
1 + Math.min(leftDepth, rightDepth)

Consider this tree:

  10
 /
5

Here, the root 10 has a left child 5 and a right child that is null.

• The minDepth of the left subtree (node 5) is 1.
• The minDepth of the right subtree (null) is 0.

If we use 1 + Math.min(1, 0), we get a result of 1. But this is wrong! The shortest path to a leaf is 10 -> 5, which has a depth of 2. A path must end at a leaf node, which is a node with no children. The root node 10 is not a leaf.

This highlights a critical point: you must always be precise about the problem's constraints. The simple min-based formula fails because it incorrectly treats a path to a null node as a valid, completed path of length 0.

The correct logic is:

• If a node has both left and right children, then we can safely take the minimum of their depths.
• If a node has only one child, we are forced to follow that path. We cannot stop. We must take the depth of the non-null subtree.

This resource from Algo.monster explains this nuance perfectly.

Here is the corrected TypeScript code for minDepth, which handles the single-child case explicitly.

function minDepth(root: TreeNode | null): number {
    // Base Case: An empty tree has depth 0.
    if (root === null) {
        return 0;
    }

    // If one child is null, we MUST go down the other path.
    // We can't stop here, as this is not a leaf node.
    if (root.left === null) {
        return 1 + minDepth(root.right);
    }
    if (root.right === null) {
        return 1 + minDepth(root.left);
    }

    // Only if both children exist can we choose the shorter path.
    return 1 + Math.min(minDepth(root.left), minDepth(root.right));
}

By comparing maxDepth and minDepth, you can see how a single underlying pattern can be adapted to solve different problems by carefully considering the specific constraints of each.

Conclusion

In this lesson, you've learned one of the most fundamental patterns for solving tree problems. This "post-order" recursive approach, where you get answers from your children and combine them, is a powerful mental model.

Here are the key takeaways:

• The Recursive Pattern: For many tree problems, you can define a solution in terms of the solutions for its subtrees: (1) handle base cases, (2) recurse on children, (3) combine results.
• "Bubbling Up" Information: This pattern works by passing computed values up the call stack, from the leaves back to the root.
• Maximum Depth: A straightforward application of the pattern: 1 + max(left, right).
• Precision is Key: A small change in the problem statement, like from "maximum" to "minimum" depth, can introduce important edge cases (like handling single-child nodes) that require you to adapt the combination logic.

In our next lesson, we will explore another recursive pattern for trees. Instead of "bubbling up" results, we will learn how to pass information down the tree to enforce constraints, which is essential for problems like validating a Binary Search Tree.