Crack the Backend

Problem Statement

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

Empty tree (root is null): depth is 0. Single node: depth is 1. We can define depth recursively: depth(root) = 0 if root == null; else 1 + max(depth(left), depth(right)).

Key Observations

Recursive definition: The depth of a node is 0 if the node is null. Otherwise it is 1 plus the maximum of the depths of its left and right subtrees. So maxDepth(root) = 1 + max(maxDepth(root.left), maxDepth(root.right)) with base case root == null -> 0.
Alternatively, use BFS (level order) and count levels; or DFS with an explicit stack and track current depth. The recursive solution is the simplest.

Approach

High-level: If root == null return 0. Return 1 + max(maxDepth(root.left), maxDepth(root.right)).

Steps:

if root == null return 0.
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right)).

Implementation

Java

public int maxDepth(TreeNode root) {

    if (root == null) {
        return 0;
    }

    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

Test Cases

Example 1

Input

root = [3,9,20,null,null,15,7]

Expected

3

Explanation

Longest path has 3 nodes.

Complexity Analysis

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

Follow-ups

Minimum depth; diameter of tree.