Maximum Depth of Binary Tree

The depth of a tree is 1 (for the root) plus the deeper of its two subtrees. An empty tree has depth 0. Recursion computes it bottom-up: each node waits for its children's depths.

Traced input: root = [3, 9, 20, null, null, 15, 7] → 3. Original problem: neetcode.io/problems/depth-of-binary-tree

Complexity

Every node is visited once; the call stack is as deep as the tree (h), O(n) for a skewed tree.

Key idea

• Base case: null has depth 0.
• Recursive case: 1 + max(depth(left), depth(right)).
• BFS counting levels gives the same answer iteratively.

Common mistakes

• Returning 1 for a null node (off by one).
• Very deep skewed trees can overflow the call stack; BFS avoids recursion.

Solution

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

def maxDepth(root: Optional[TreeNode]) -> int:
    if not root: return 0
    left = maxDepth(root.left)
    right = maxDepth(root.right)
    return 1 + max(left, right)

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

Edge cases

Each one has its own trace in the interactive view.