Maximum Depth of Binary Tree

Approach Summary

Recursively: max(leftDepth, rightDepth) + 1. Null node returns 0.

Full Solution & Approach

The depth of a tree is 1 (the root) plus the depth of the deeper child. Recursion falls directly out of this: for a null node return 0; otherwise return 1 + max(maxDepth(left), maxDepth(right)). This is post-order traversal — the children must be resolved before the parent can combine their depths. Every node is visited exactly once, so the time is O(n). Space is the recursion depth, which equals the tree height: O(h), worst case O(n) for a skewed tree (which is also a stack-overflow risk — an iterative BFS that counts levels handles that case). This is often the first tree problem people solve, and it establishes the recursion pattern used by balanced-tree checks, diameter, and path-sum problems.

Each node is visited once with constant work — O(n) time. Recursion depth equals the height — O(h) space, worst case O(n) for a skewed tree.

Solution Code

Solution

def max_depth(root) -> int:
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

function maxDepth(root) {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

int maxDepth(TreeNode* root) {
    if (!root) return 0;
    return 1 + max(maxDepth(root->left), maxDepth(root->right));
}

Edge Cases to Watch

Empty tree — return 0
Single node — return 1
Skewed left or right tree — depth equals the node count
Pathologically deep tree — recursion depth equals height; use iterative BFS to avoid stack overflow

How to Recognize This Pattern

Tree height/depth

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(h)