Maximum depth of Binary Tree

Problem Link

Maximum Depth of Binary Tree – LeetCode

Problem: Maximum Depth of Binary Tree

Problem Statement

Given the root of a binary tree, return its maximum depth.

The maximum depth of a binary tree is the number of nodes along the longest path from the root node down to the farthest leaf node.

Examples

Example 1

Input:

     3
    / \
   9  20
      / \
     15  7

Output: 3

Example 2

Input:

root = [1,null,2]

Output: 2

Constraints

• 0 <= number of nodes <= 10⁴

• -100 <= Node.val <= 100

Intuition

To compute the maximum depth of a binary tree, we can break the problem into:

• Finding the maximum depth of the left subtree

• Finding the maximum depth of the right subtree

• Taking the maximum of the two and adding 1 (for the current node)

This is a classical application of recursion.

Approach (Recursion using Induction – Base Case – Hypothesis)

1. Base Case:

If the node is null, return 0 (depth of empty tree is 0)

2. Hypothesis:

Assume that maxDepth(root.left) and maxDepth(root.right) give correct depth of left and right subtree.

3. Induction:

Return 1 + max(leftDepth, rightDepth) as the final answer.

Code (Java)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class Solution {
    public int maxDepth(TreeNode root) {
        // Base case
        if (root == null) return 0;

        // Hypothesis
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);

        // Induction
        return 1 + Math.max(leftDepth, rightDepth);
    }
}

Time and Space Complexity

• Time Complexity: O(N)
  Each node is visited once.

• Space Complexity: O(H)
  Stack space used by recursion. H is height of tree (O(log N) for balanced, O(N) for skewed).

Dry Run

Input:

       1
        \
         2
          \
           3

Call stack:

• maxDepth(1) → 1 + max(0, maxDepth(2))

• maxDepth(2) → 1 + max(0, maxDepth(3))

• maxDepth(3) → 1 + max(0, 0) = 1

• maxDepth(2) → 1 + max(0, 1) = 2

• maxDepth(1) → 1 + max(0, 2) = 3

Conclusion

This problem highlights how to reduce a problem to its substructure using recursion.
It's a perfect case for divide and conquer, and reinforces the idea of thinking recursively in trees.