1. Problem Summary

You are given the root of a binary tree. Your task is to determine the maximum depth of the tree.

The depth of a binary tree is defined as:

• the total number of nodes along the longest path
• starting from the root node
• down to the farthest leaf node

A leaf node is one that has no left or right child.

Example understanding:
If the longest path contains nodes [1 → 3 → 6 → 9], the depth is 4.

---

2. Key Insights

Depth is measured in node count, not edges

Some problems count edges, but here we count nodes.

Recursive structure of trees

The depth of a tree can be expressed as:

depth = 1 + max(depth(left subtree), depth(right subtree))

Base case is important

If the node is null, its depth is zero.

Can be solved using DFS or BFS

DFS naturally fits recursion.
BFS level-order traversal counts layers.

---

3. Approach

Recursive Depth-First Search (DFS)

1. If the current node is null, return 0.
2. Recursively compute depth of left subtree.
3. Recursively compute depth of right subtree.
4. The depth of current node is: 1 + max(leftDepth, rightDepth)
5. Return the computed depth.

This directly mirrors the mathematical definition of a tree’s height.

---

4. Time and Space Complexity

Time Complexity: O(N)

You must visit every node once.

Space Complexity:

• O(H) due to recursion call stack
• H = height of tree
• Worst case (skewed tree): O(N)
• Best case (balanced tree): O(log N)

---

5. Java Solution

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

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

---

6. Dry Run Example

Consider the tree:

        3
      /   \
     9     20
          /  \
         15   7

Step-by-step evaluation:

Node 15

Left child: null → depth 0
Right child: null → depth 0
Depth = 1 + max(0, 0) = 1

Node 7

Depth = 1 for same reasoning

Node 20

Left depth = 1
Right depth = 1
Depth = 1 + max(1, 1) = 2

Node 9

Depth = 1 (leaf node)

Root node 3

Left depth = 1
Right depth = 2
Depth = 1 + max(1, 2) = 3

Final output: 3

---

7. BFS Alternative (Iterative)

import java.util.LinkedList;
import java.util.Queue;

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

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            depth++;

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();

                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }

        return depth;
    }
}

When BFS is useful:

• when you want to count levels explicitly
• when avoiding recursion stack is desired