Max Depth of Binary Tree

The maximum depth of a binary tree is the number of nodes along the longest path from the root node down to the farthest leaf node. This fundamental tree property is often needed for algorithms that process trees level by level or need to understand tree balance.

How it Works

Calculating the maximum depth of a binary tree can be done efficiently using a recursive depth-first search approach. The core idea is that the maximum depth of a tree is one plus the maximum depth of its left or right subtree.

Base Case

The recursion starts by checking if the current node is null. If it is, this signifies an empty tree or a non-existent child, and its depth is `0`.

Recursive Steps

For a non-null node, the algorithm recursively calls itself on the left child to determine the maximum depth of the left subtree. It then does the same for the right child to find the maximum depth of the right subtree. Once these two values are obtained, the maximum of the two is taken, and `1` is added to account for the current node itself.

For example, consider a tree with root `3`, left child `9`, and right child `20`. The process unfolds:

1. Start at root node `3`: The function is called for node `3`. 2. Recurse left to node `9`: The function is called for node `9`. Since `9` has no children, its left and right subtree depths are `0`. It returns `max(0, 0) + 1 = 1`. 3. Recurse right to node `20`: The function is called for node `20`. Similar to `9`, it has no children, so it returns `max(0, 0) + 1 = 1`. 4. Combine results at root `3`: Back at node `3`, we have the left depth (`1`) and the right depth (`1`). The final depth for the tree rooted at `3` is `max(1, 1) + 1 = 2`.

function max_depth(node):
    if node is null:
        return 0
    
    left_depth = max_depth(node.left)
    right_depth = max_depth(node.right)
    
    return max(left_depth, right_depth) + 1

Key Takeaways

• The maximum depth is the longest path from the root to any leaf.
• A recursive depth-first approach is highly effective.
• The base case for an empty tree (null node) is a depth of `0`.
• The depth of a non-null node is `1` plus the maximum depth of its subtrees.
• This method efficiently explores all paths without explicit path tracking.