Problem Description

You are given the root of a binary tree. Your task is to find the maximum depth of the tree.

The maximum depth is defined as the number of nodes along the longest path from the root node down to the farthest leaf node. In other words, it's the length of the longest root-to-leaf path in the tree, counting the nodes themselves.

For example:

• If the tree is empty (root is None), the maximum depth is 0
• If the tree has only a root node with no children, the maximum depth is 1
• If the tree has multiple levels, you need to find the deepest leaf and count how many nodes are on that path from root to leaf

The solution uses a recursive approach where:

1. If we reach a None node (empty tree or beyond a leaf), we return depth 0
2. For any non-empty node, we recursively calculate the maximum depth of its left subtree and right subtree
3. The depth at the current node is 1 (for the current node itself) plus the maximum of the depths from the left and right subtrees: 1 + max(left_depth, right_depth)

This way, the recursion builds up the depth count from the bottom (leaves) to the top (root), ultimately returning the maximum depth of the entire tree.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: A binary tree is a special type of graph where each node has at most two children and there are no cycles.

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree structure.

DFS

• We arrive at DFS (Depth-First Search) as our algorithm choice.

Conclusion: The flowchart suggests using DFS (Depth-First Search) for finding the maximum depth of a binary tree.

This makes perfect sense because:

1. Trees are acyclic connected graphs, making them ideal for DFS traversal
2. Finding the maximum depth requires exploring all paths from root to leaves
3. DFS naturally explores each path completely before backtracking, which aligns perfectly with calculating the depth of each path
4. The recursive nature of DFS matches the recursive structure of trees, where we can solve the problem by combining solutions from subtrees

The solution implements DFS recursively by:

• Visiting each node (starting from root)
• Recursively calculating depths of left and right subtrees
• Returning 1 + max(left_depth, right_depth) to build up the maximum depth from bottom to top

Intuition

When we think about finding the maximum depth of a tree, we need to understand what depth means - it's the number of nodes from root to the farthest leaf. This immediately suggests we need to explore all possible paths from root to leaves.

The key insight is that a tree's maximum depth can be broken down into smaller subproblems. For any node, the maximum depth passing through that node is:

• 1 (for the current node itself)
• Plus the maximum depth of either its left or right subtree

This recursive relationship naturally emerges because trees have a recursive structure - each subtree is itself a complete tree with its own maximum depth.

Think of it like measuring the height of a corporate hierarchy: to find the total levels from CEO to the lowest employee, you'd ask each direct report "what's the maximum depth in your department?" Then you'd take the largest answer and add 1 (for the CEO level itself).

The base case becomes clear when we reach a leaf's children (which are None) - there's no depth beyond that point, so we return 0. This allows the recursion to "bubble up" from the leaves back to the root, with each level adding 1 to the maximum depth found below it.

The elegance of this DFS approach is that it mirrors the tree's structure perfectly - we're essentially asking each node "what's the deepest path beneath you?" and building our answer from the bottom up. The recursive calls handle all the traversal automatically, visiting every node exactly once to determine the overall maximum depth.

Solution Approach

The solution implements a recursive DFS approach to find the maximum depth of the binary tree. Let's walk through the implementation step by step:

Base Case:

if root is None:
    return 0

When we encounter a None node (either an empty tree or we've gone past a leaf node), we return 0 as there's no depth to count.

Recursive Case:

l, r = self.maxDepth(root.left), self.maxDepth(root.right)

For any non-null node, we recursively calculate:

• l: the maximum depth of the left subtree
• r: the maximum depth of the right subtree

These recursive calls will traverse down to the leaves and return the depths from bottom to top.

Combining Results:

return 1 + max(l, r)

The maximum depth at the current node is:

• 1 for counting the current node itself
• Plus the maximum of the left and right subtree depths

This ensures we're always taking the longest path from the current node down to any leaf.

How the Recursion Unfolds:

The algorithm works by traversing the tree in a depth-first manner:

1. It goes as deep as possible in the left subtree first
2. When it hits None nodes, it returns 0
3. As the recursion unwinds, each level adds 1 to the maximum depth found below
4. The same process happens for the right subtree
5. At each node, we take the maximum of left and right depths

Time and Space Complexity:

• Time: O(n) where n is the number of nodes, as we visit each node exactly once
• Space: O(h) where h is the height of the tree, due to the recursion call stack. In the worst case (skewed tree), this could be O(n)

Example Walkthrough

Let's walk through finding the maximum depth of this binary tree:

        1
       / \
      2   3
     /
    4

Step-by-step execution:

1. Start at root (1):

   • Call maxDepth(1)
   • Need to calculate maxDepth(1.left) and maxDepth(1.right)

2. Process left subtree of 1 (node 2):

   • Call maxDepth(2)
   • Need to calculate maxDepth(2.left) and maxDepth(2.right)

3. Process left subtree of 2 (node 4):

   • Call maxDepth(4)
   • Calculate maxDepth(4.left) → returns 0 (None)
   • Calculate maxDepth(4.right) → returns 0 (None)
   • Return 1 + max(0, 0) = 1

4. Process right subtree of 2 (None):

   • Call maxDepth(None) → returns 0

5. Complete node 2:

   • Left depth = 1 (from node 4)
   • Right depth = 0 (None)
   • Return 1 + max(1, 0) = 2

6. Process right subtree of 1 (node 3):

   • Call maxDepth(3)
   • Calculate maxDepth(3.left) → returns 0 (None)
   • Calculate maxDepth(3.right) → returns 0 (None)
   • Return 1 + max(0, 0) = 1

7. Complete root node 1:

   • Left depth = 2 (from subtree with nodes 2→4)
   • Right depth = 1 (from node 3)
   • Return 1 + max(2, 1) = 3

Result: Maximum depth = 3

The algorithm correctly identifies that the longest path is 1→2→4, which contains 3 nodes.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the number of nodes in the binary tree. The algorithm performs a depth-first search traversal, visiting each node exactly once. At each node, it performs constant time operations (comparison and addition), so the total time is proportional to the number of nodes.

Space Complexity: O(h), where h is the height of the binary tree. This space is used by the recursive call stack. In the worst case, when the tree is completely unbalanced (skewed), the height h can be equal to n, making the space complexity O(n). In the best case, when the tree is perfectly balanced, the height is log(n), making the space complexity O(log n).

Common Pitfalls

1. Confusing Depth vs Height Terminology

A common mistake is misunderstanding what "depth" means in this context. Some developers confuse:

• Depth of a node: Distance from root to that specific node
• Height of a node: Distance from that node to its farthest leaf
• Maximum depth of tree: What we're calculating here - the total number of nodes on the longest root-to-leaf path

Solution: Remember that this problem asks for the maximum depth of the entire tree, which equals the height of the root node plus 1. The recursive solution correctly counts nodes (returning 1 + max(left, right)), not edges.

2. Incorrect Base Case Return Value

Some might incorrectly return 1 for the base case:

# WRONG!
if root is None:
    return 1  # This would count non-existent nodes

Solution: Always return 0 for None nodes. A None node contributes nothing to the depth count.

3. Off-by-One Errors in Counting

Developers sometimes forget to add 1 for the current node or add it incorrectly:

# WRONG - Forgets to count current node
return max(left_depth, right_depth)

# WRONG - Adds 1 twice
return 1 + max(1 + left_depth, 1 + right_depth)

Solution: Add 1 exactly once per node to account for the current node itself: return 1 + max(left_depth, right_depth)

4. Stack Overflow with Extremely Deep Trees

For very deep or unbalanced trees (like a linked list shaped tree with 10,000 nodes), the recursive solution can cause stack overflow.

Solution: Use an iterative approach with explicit stack or queue:

def maxDepth(self, root: TreeNode) -> int:
    if not root:
        return 0
  
    stack = [(root, 1)]
    max_depth = 0
  
    while stack:
        node, depth = stack.pop()
        max_depth = max(max_depth, depth)
      
        if node.left:
            stack.append((node.left, depth + 1))
        if node.right:
            stack.append((node.right, depth + 1))
  
    return max_depth

5. Not Handling Edge Cases Properly

Forgetting to test with:

• Empty tree (root = None)
• Single node tree
• Completely unbalanced tree (all nodes on one side)

Solution: Always validate your solution with these edge cases before considering it complete.