Solution Explanation: Maximum Depth of Binary Tree

This problem asks to find the maximum depth (height) of a binary tree. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Approach: Depth-First Search (DFS) - Recursive Approach

The most efficient and elegant solution uses a recursive Depth-First Search (DFS) approach. The core idea is as follows:

1. Base Case: If the current node (root) is null (empty), the depth is 0.

2. Recursive Step: Otherwise, recursively calculate the maximum depth of the left subtree (leftDepth) and the right subtree (rightDepth).

3. Maximum Depth: The maximum depth of the current node is 1 (for the current node itself) plus the maximum of leftDepth and rightDepth.

Code Explanation (Python as an example, but the logic is the same across all languages):

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
 
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root is None:  # Base case: empty tree
            return 0
        leftDepth = self.maxDepth(root.left) # Recursive call for left subtree
        rightDepth = self.maxDepth(root.right) # Recursive call for right subtree
        return 1 + max(leftDepth, rightDepth) # 1 + max depth of subtrees
 

Time and Space Complexity Analysis:

• Time Complexity: O(N), where N is the number of nodes in the binary tree. This is because each node is visited exactly once during the traversal.

• Space Complexity: O(H), where H is the height of the binary tree. This space is used for the recursion stack. In the worst-case scenario (a skewed tree), H can be equal to N. In the best-case scenario (a balanced tree), H is log₂(N).

Other Approaches:

While recursion is the most concise and often preferred method, you could also solve this using Breadth-First Search (BFS) with a queue. However, BFS would generally have a slightly higher space complexity due to the queue storing nodes at each level. The time complexity remains O(N) for both approaches.

The provided code solutions in various programming languages demonstrate the same recursive DFS algorithm. They differ only in syntax and specific library functions (e.g., Math.max vs. max). The core logic remains identical across all implementations.