Maximum Depth of Binary Tree

Given the root of a binary tree, return its maximum depth (number of nodes along the longest path from root to leaf).

Function signature

func MaxDepth(root *TreeNode) int

Inputs / outputs

• root: pointer to the root node.
• Return: maximum depth.

Example

    3
   / \
  9  20
     / \
    15  7
Output: 3

Constraints

• 0 <= number of nodes <= 100_000

Core idea (near-solution)

Depth of a node is 1 + max(depth of left, depth of right).

Invariant: recursion returns correct depth for each subtree.

Algorithm (step-by-step)

1. If node is nil, return 0.
2. Recursively compute left and right depths.
3. Return 1 + max(left, right).

Correctness sketch

• Invariant: recursion returns correct depth for each subtree.
• Base cases handle nil/leaf nodes correctly.
• Recursive calls return correct results for subtrees (induction).
• Combining subtree results yields the correct answer for the current node.

Trace (hand walkthrough)

Example input:
    3
   / \
  9  20
     / \
    15  7
Output: 3

Walk:
- leaf 9 has depth 1; leaves 15 and 7 have depth 1
- node 20 depth = 1 + max(1,1) = 2
- root 3 depth = 1 + max(1,2) = 3

Pitfalls to avoid

• Forgetting the base case for nil.

Complexity

• Time: O(n)
• Extra space: O(h) recursion stack.

Implementation notes (Go)

• Handle root == nil early.
• DFS recursion is simplest; BFS works if stack depth is a concern.