Maximum Depth of a Binary Tree

Determining the maximum depth of a binary tree is a fundamental problem in tree traversal and a common interview question. The depth of a tree is the number of nodes along the longest path from the root node to the farthest leaf node. This problem is useful for understanding tree structures and recursive algorithms.

Problem Description

Given the root node of a binary tree, calculate and return its maximum depth. The depth of a single node is 1. An empty tree has a depth of 0. You must consider all possible paths from the root to leaf nodes to find the longest one.

What needs to be achieved: Calculate the maximum number of edges from the root node to the furthest leaf node in the binary tree.

Key requirements:

• Handle empty trees gracefully.
• Correctly calculate the depth even with unbalanced trees.
• The solution should be efficient.

Expected behavior: The function should take the root node of a binary tree as input and return an integer representing the maximum depth.

Edge cases to consider:

• Empty tree (root is null).
• Tree with only a root node.
• Unbalanced trees (trees where one branch is significantly longer than others).
• Trees with only left or right children.

Examples

Example 1:

Input:
    3
   / \
  9  20
    /  \
   15   7

Output: 3 Explanation: The longest path from the root (3) to a leaf node is 3 -> 20 -> 15 or 3 -> 20 -> 7, both having a depth of 3.

Example 2:

Input:
   1

Output: 1 Explanation: The tree consists of only the root node, so the depth is 1.

Example 3:

Input: null

Output: 0 Explanation: The tree is empty, so the depth is 0.

Constraints

• The binary tree can have up to 10⁵ nodes.
• The values of the nodes are not relevant to the problem; only the structure matters.
• The solution should have a time complexity of O(N), where N is the number of nodes in the tree, to ensure efficient traversal.
• The solution should have a space complexity of O(H), where H is the height of the tree, due to the recursive call stack. In the worst case (skewed tree), H can be N, but in a balanced tree, H will be log(N).

Notes

A recursive approach is often a natural fit for this problem. Consider how the depth of a subtree can be calculated based on the depths of its children. Think about the base case for the recursion – when should it stop? You can also solve this iteratively using a stack or queue (Breadth-First Search).