Problem

Given the root of a binary tree, return its maximum depth (the longest path from the root to any leaf).

Example

Input:  [3,9,20,null,null,15,7]
Output: 3

Solution

Recursive: depth = 1 + max(depth of left, depth of right).

def max_depth(root):
    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));
}

int maxDepth(TreeNode* root) {
    if (!root) return 0;
    return 1 + 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));
}

Complexity

• Time: O(n)
• Space: O(h) recursion stack

Explanation

Classic tree recursion. Each node contributes 1 to the depth, plus whichever child subtree is deeper.