1. Understanding the Problem

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

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

A leaf node is a node with no children (both left and right pointers are null).

The Core Constraint (The Trap):

Trees are non-linear data structures. You cannot calculate the depth in a single linear pass like an array. Additionally, if you use a recursive approach on a heavily skewed tree (where every node only has one child, looking like a linked list), a deep call stack can cause a StackOverflowError if not properly accounted for.

2. The Intuitive Approach: Recursive Depth-First Search (DFS)

The most elegant and standard way to solve this problem is by using Recursion (Post-Order Traversal). We divide the big tree into smaller subproblems.

To find the maximum depth of any node, ask its left and right children: "What is your maximum depth?" Once both children answer, the depth of the current node is simply 1 + max(left_depth, right_depth).

Trade-off Analysis

• Time Complexity: O(N) — We visit every node in the tree exactly once.
• Space Complexity: O(H) — Where H is the height of the tree. In a balanced tree, space complexity is O(log N). However, in the worst-case scenario (a skewed tree), the recursion stack grows to O(N).

3. The Alternative Approach: Iterative Breadth-First Search (BFS)

In a senior-level interview, after providing the recursive solution, your interviewer might ask: "How would you solve this iteratively to avoid stack overflow risks?"

We can solve this iteratively by using a Queue to traverse the tree level-by-level (Breadth-First Search). Imagine a scanner moving down a tree line by line. Every time we finish scanning all nodes at the current level, we increment our depth counter by 1 and move to the next level down.

4. The Logic Step-by-Step (Recursive DFS)

1. Base Case: Check if the current node is null. If it is, return 0 (an empty tree has a depth of 0).
2. Recurse Left: Calculate the max depth of the left subtree: left_depth = maxDepth(node.left).
3. Recurse Right: Calculate the max depth of the right subtree: right_depth = maxDepth(node.right).
4. Combine Results: Return 1 + max(left_depth, right_depth). The 1 accounts for the current node itself.

5. Complexity Analysis

• Time Complexity: O(N) — Each node is processed exactly once regardless of whether you use DFS or BFS.
• Space Complexity: O(H) for Recursive DFS (where H is the tree height due to the function call stack) and O(W) for Iterative BFS (where W is the maximum width of the tree, representing the queue size).

6. Code Implementations

Expand the sections below to see the clean, optimal Recursive DFS implementations across different 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: Optional[TreeNode]) -> int:
        # Base Case: Empty node contributes 0 to depth
        if not root:
            return 0
            
        # Divide & Conquer: Find max depth of left and right subtrees
        left_depth = self.maxDepth(root.left)
        right_depth = self.maxDepth(root.right)
        
        # Current node depth is 1 + maximum of child depths
        return 1 + max(left_depth, right_depth)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        // Base Case
        if (root == null) {
            return 0;
        }
        
        // Recurse on left and right subtrees
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        
        // Return 1 (current node) + max depth of subtrees
        return 1 + Math.max(leftDepth, rightDepth);
    }
}

#include <algorithm>

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        // Base Case
        if (root == nullptr) {
            return 0;
        }
        
        // Compute the depth of each subtree
        int leftDepth = maxDepth(root->left);
        int rightDepth = maxDepth(root->right);
        
        // Return max depth among children + 1 for current node
        return 1 + std::max(leftDepth, rightDepth);
    }
};

7. Conclusion: You Are Ready

Congratulations, you have just mastered the cornerstone problem of tree recursion! Calculating the depth of a binary tree introduces you to the core concept of bottom-up divide-and-conquer processing. Mastering both the elegant recursive DFS approach and the level-by-level BFS approach demonstrates a well-rounded understanding of tree traversals. Keep this pattern handy—it forms the exact building block for solving problems like Balanced Binary Tree, Minimum Depth of Binary Tree, and Same Tree!