Maximum Depth of Binary Tree

easy tree dfs recursion

Problem

Given the root of a binary tree, return its maximum depth. A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Inputlevel-order: [4, 2, 7, 1, 3, _, 9]

Output3

The tree has root 4, depth 3 along 4→2→1 (or 4→2→3 or 4→7→9).

level-order ('_' for null)

def max_depth(root):
    if root is None:
        return 0
    l = max_depth(root.left)
    r = max_depth(root.right)
    return 1 + max(l, r)

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

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

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

Explanation

The depth of a tree has a beautifully simple recursive definition: a tree is one node (the root) sitting on top of its deeper child. So its depth is 1 + the depth of its taller subtree.

The base case handles emptiness: an empty tree (root is None) has depth 0. This is what lets the recursion bottom out.

For any real node we recursively measure l = maxDepth(left) and r = maxDepth(right), then return 1 + max(l, r). We pick the larger child because depth follows the longest root-to-leaf path.

Example: [4, 2, 7, 1, 3, _, 9]. A leaf like 1 reports depth 1; node 2 reports 1 + max(1, 1) = 2; the root 4 reports 1 + max(2, 2) = 3, which is the answer.

Every node is visited exactly once, so this runs in O(n) time.

Time: O(n) Space: O(h) recursion depth