Maximum Depth of Binary Tree

Problem

Given the root of a binary tree, return its maximum depth.

A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 3

Example 2:

Input: root = [1,null,2]
Output: 2

Constraints:

The number of nodes in the tree is in the range [0, 10^4].
-100 <= Node.val <= 100

Solution

Approach 1: Recursive DFS

The key insight is that the depth of a tree is 1 + the maximum depth of its subtrees.

Implementation

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        left_depth = self.maxDepth(root.left)
        right_depth = self.maxDepth(root.right)

        return 1 + max(left_depth, right_depth)

Concise Version:

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

Approach 2: Iterative BFS

Use a queue to process nodes level by level, counting the number of levels.

from collections import deque

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        queue = deque([root])
        depth = 0

        while queue:
            depth += 1
            # Process all nodes at current level
            for _ in range(len(queue)):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

        return depth

Complexity Analysis

Recursive:

Time Complexity: O(n), where n is the number of nodes. We visit each node once.
Space Complexity: O(h), where h is the height of the tree (recursion stack).

Iterative:

Time Complexity: O(n), we visit each node once.
Space Complexity: O(w), where w is the maximum width of the tree.

Key Insights

Recursive Definition: The depth of a tree equals 1 (current node) plus the maximum depth of its left and right subtrees.
Base Case: An empty tree (null node) has depth 0.
Post-Order Traversal: The recursive solution follows post-order traversal - we compute depths of children before computing the parent’s depth.
Level-by-Level: The BFS approach counts levels explicitly, making the depth calculation straightforward.
Height vs Depth: Maximum depth equals the height of the tree - the longest path from root to leaf.