Maximum Depth of a Binary Tree

easy tree dfs recursion

Problem

Given the root of a binary tree, return the length of the longest path from the root down to any leaf (counted in nodes). The depth of an empty tree is zero. A one-line recursion is enough: depth(node) = 1 + max(depth(left), depth(right)).

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);
}

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