Tree Height and Depth

Concept

In interviews, the terms Depth and Height are often used interchangeably, but in strict computer science terminology, they mean opposite things:

• Depth: The distance from the Root DOWN to a specific Node. (The Root has a Depth of 0).
• Height: The distance from a specific Node DOWN to the deepest Leaf. (A Leaf has a Height of 0).

The Maximum Depth of a tree and the Height of the Root are mathematically the exact same number.

Maximum Depth of Binary Tree

Problem: Given the root of a binary tree, return its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. (LeetCode 104).

We already solved this using a Bottom-Up Post-order Traversal in a previous section.

function maxDepth(root: TreeNode | null): number {
    if (root === null) return 0;
    
    // Bottom-Up approach:
    const leftDepth = maxDepth(root.left);
    const rightDepth = maxDepth(root.right);
    
    return Math.max(leftDepth, rightDepth) + 1;
}

Minimum Depth of Binary Tree

Problem: Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. (LeetCode 111).

This seems identical to Maximum Depth. Just change Math.max to Math.min, right?
Wrong. That is the classic trap.

Imagine a Root node that only has a Right child. The Left branch is null.
If you use Math.min(left, right), the Left branch returns 0. The formula will calculate Math.min(0, right) + 1 = 1.
The algorithm thinks the minimum depth is 1, stopping at the Root! But the Root is not a Leaf node (it has a right child!). A Leaf node is strictly defined as a node with ZERO children.

We must add explicit if statements to ignore empty branches.

function minDepth(root: TreeNode | null): number {
    if (root === null) return 0;

    // If there is no left child, we MUST traverse down the right child!
    if (root.left === null) {
        return minDepth(root.right) + 1;
    }
    
    // If there is no right child, we MUST traverse down the left child!
    if (root.right === null) {
        return minDepth(root.left) + 1;
    }

    // Both children exist. We can safely find the minimum path.
    return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
}

The BFS Optimization for Minimum Depth

While DFS solves Minimum Depth, it is actually highly inefficient.
If a tree has a leaf at Level 2 on the right side, but the left side goes down 10,000 levels, DFS will plunge all the way down the 10,000 levels first before it ever discovers the tiny right branch.

Breadth-First Search (BFS) is vastly superior for “Minimum” problems. Because BFS scans horizontally level-by-level, the absolute first time it encounters a Leaf node, it is mathematically guaranteed to be the shortest path! It instantly returns the depth and aborts, saving massive amounts of time.

function minDepthBFS(root: TreeNode | null): number {
    if (root === null) return 0;
    
    const queue: TreeNode[] = [root];
    let depth = 1;
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift()!;
            
            // Is this a Leaf Node? (No left, No right)
            if (node.left === null && node.right === null) {
                return depth; // We found the absolute closest leaf! Exit instantly.
            }
            
            if (node.left !== null) queue.push(node.left);
            if (node.right !== null) queue.push(node.right);
        }
        
        depth++; // Increment depth after finishing a full horizontal level
    }
    
    return depth;
}

Interview Questions

Q: In the “Diameter of a Binary Tree” problem, you must find the length of the longest path between any two nodes in a tree (the path does not need to pass through the root). How is this related to tree height?
A: The diameter of any specific node is exactly mathematically defined as Left_Height + Right_Height.
To solve the problem, you run the standard Bottom-Up maxDepth DFS function. But as the recursion bubbles up, you introduce a global maxDiameter variable. At every single node, right before you return Math.max(left, right) + 1, you calculate the local diameter (left + right) and update the global maxDiameter if the local one is larger. This solves it elegantly in $O(N)$ time.