Maximum Depth of a Binary Tree

Given the root of a binary tree, determine 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. This is a fundamental concept in understanding tree structures and is crucial for various tree algorithms and analyses.

Problem Description

You are tasked with writing a function that calculates the maximum depth of a given binary tree. The depth of a tree is defined as the number of nodes along the longest path from the root node to any leaf node.

Requirements:

• The function should accept the root node of a binary tree as input.
• The function should return an integer representing the maximum depth of the tree.

Expected Behavior:

• For an empty tree (null root), the depth should be 0.
• For a tree with only a root node, the depth should be 1.
• For a tree with multiple nodes, the depth should be the count of nodes on the longest path from the root to a leaf.

Edge Cases:

• An empty tree.
• A tree with only a single node.

Examples

Example 1:

Input:
    3
   / \
  9  20
    /  \
   15   7

Output: 3
Explanation: The longest path is 3 -> 20 -> 15 (or 3 -> 20 -> 7), which has 3 nodes.

Example 2:

Input:
    1
     \
      2

Output: 2
Explanation: The longest path is 1 -> 2, which has 2 nodes.

Example 3:

Input: null

Output: 0
Explanation: An empty tree has a depth of 0.

Constraints

• The number of nodes in the tree will be between 0 and 10^4.
• Node values can be any integer.
• The solution should aim for an efficient time complexity.

Notes

• A binary tree node typically has a value and references to its left and right children.
• Consider how you might traverse the tree to find the longest path. Recursion is a common and elegant approach for tree problems.
• Think about the base cases for your traversal.