LeetCode 104: Maximum Depth of Binary Tree in C++: Recursive DFS Explained

Disclaimer

This article is an independent educational explanation of a programming problem originally published on LeetCode. The original problem statement, examples, constraints, trademarks, and related materials belong to LeetCode and their respective rights holders.

The real-world scenario is a hypothetical educational adaptation and does not represent a confirmed company process unless explicitly stated with a reliable source.

The solution, explanation, and code are for learning and reference. Other valid approaches may exist. Readers should verify current requirements on the original LeetCode page.

Article Summary

In this problem, we need to find the number of nodes on the longest path from the root of a binary tree to its farthest leaf.

A binary tree is naturally recursive: every node can be viewed as the root of its own smaller left and right subtrees. Because of this structure, recursive depth-first search (DFS) is a direct and efficient solution.

For each node, we calculate the maximum depth of its left subtree and the maximum depth of its right subtree. The current node then returns one plus the larger of those two depths.

This article explains how to recognize that recursive relationship, implement it safely in C++, prove that it works, and analyze its time and auxiliary space complexity.

Original Problem and Credit

This article is based on the LeetCode problem “Maximum Depth of Binary Tree.”

• Original problem: LeetCode 104 — Maximum Depth of Binary Tree
• Platform: LeetCode
• Original problem, examples, and constraints credit: LeetCode
• Explanation, adaptation, analysis, and commentary: Andy

This article summarizes the problem in original language rather than reproducing the full LeetCode statement.

Original Problem in Simple Terms

We are given the root of a binary tree.

Our task is to return the tree's maximum depth, defined as the number of nodes on the longest path from the root to any leaf.

A leaf is a node with no left or right child.

Important cases include:

• An empty tree has depth 0.
• A tree containing only its root has depth 1.
• For a non-empty tree, its maximum depth is one plus the greater depth of its two subtrees.

Constraints

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

The node values do not affect the result. Only the structure of the tree matters.

Real-World Scenario

Consider a hypothetical data-processing platform that organizes a workflow as a binary dependency tree.

Each processing task can trigger at most two downstream tasks:

• a left downstream task;
• a right downstream task.

The platform wants to estimate the deepest dependency chain before a workflow finishes. The depth is measured by counting how many tasks appear from the initial task to the farthest terminal task.

For example, suppose the initial task launches two branches. One branch finishes immediately, while the other launches additional tasks. The platform must follow the longer branch when calculating the workflow's maximum dependency depth.

This scenario is hypothetical and is used only to illustrate the algorithm.

Examples

Example 1

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

A longest root-to-leaf path is:

3 -> 20 -> 15

Another longest path is:

3 -> 20 -> 7

Each path contains three nodes, so the maximum depth is 3.

Example 2

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

The longest path is:

1 -> 2

It contains two nodes, so the maximum depth is 2.

Mapping to the Original Problem

The workflow scenario preserves the original tree problem exactly.

The adapted scenario does not change the input type, output type, tree structure, ordering rules, or expected results.

Solution Intuition

The most important observation is that every subtree is itself a binary tree.

Suppose we are currently at a node called root. Any path from this node to a leaf must continue through one of two places:

1. the left subtree;
2. the right subtree.

Therefore, the longest path beginning at the current node must use the deeper of those two subtrees.

We can express this relationship as:

maximum depth of current tree
= 1 + max(maximum depth of left subtree,
          maximum depth of right subtree)

The 1 counts the current node.

This gives us a recursive solution because finding the depth of the left or right subtree is the same type of problem as finding the depth of the original tree.

Base Case

Every recursive function needs a condition that stops further recursion.

When root == nullptr, there is no node to count, so the depth is 0:

if (root == nullptr) {
    return 0;
}

This also handles an entirely empty input tree.

Recursive Case

For a non-null node:

1. recursively calculate the left subtree's depth;
2. recursively calculate the right subtree's depth;
3. select the larger depth;
4. add 1 for the current node.

int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);

return 1 + max(leftDepth, rightDepth);

Why Depth-First Search Fits

Depth-first search explores a branch before returning to examine other branches. In this solution, recursive calls descend through the tree until they reach null child pointers.

As recursion returns, each node receives the depths of its two subtrees and computes its own result. This bottom-up combination matches the recursive definition of tree depth directly.

No additional data structure is required because the program's call stack keeps track of the active path.

Algorithm

1. Receive the current node root.
2. If root is nullptr, return 0.
3. Recursively calculate the maximum depth of root->left.
4. Recursively calculate the maximum depth of root->right.
5. Take the larger of the two subtree depths.
6. Add 1 to count the current node.
7. Return the resulting depth.

Why the Algorithm Works

We use the following invariant:

For every node passed to maxDepth, the function returns the exact number of nodes on the longest path from that node to a leaf in its subtree.

Base Case

If the current node is nullptr, its subtree contains no nodes. Returning 0 is therefore correct.

Recursive Step

Assume the recursive calls correctly return:

• the maximum depth of the left subtree;
• the maximum depth of the right subtree.

Every path from the current node to a leaf must enter either the left subtree or the right subtree. The longest such path must therefore continue through the subtree with the larger maximum depth.

The algorithm takes that larger depth and adds 1 for the current node. Thus, it returns the exact maximum depth of the tree rooted at the current node.

By recursion, this reasoning applies to every subtree. Therefore, the value returned for the original root is the maximum depth of the entire binary tree.

Complexity Analysis

Let n be the number of nodes in the binary tree, and let h be the height of the tree.

Time Complexity

O(n)

The algorithm visits each node exactly once.

At each node, it performs constant-time work outside the recursive calls:

• checking whether the pointer is null;
• storing the two returned depths;
• comparing the depths;
• adding 1.

Therefore, the total time complexity is O(n).

Space Complexity

O(h)

The algorithm does not create an input-dependent container, but recursive calls consume call-stack space.

The maximum number of simultaneous recursive calls equals the height of the tree:

• For a balanced binary tree, h = O(log n).
• For a completely skewed binary tree, h = O(n).

Therefore, the auxiliary space complexity is O(h), which becomes O(n) in the worst case.

Corrected Solution: Recursive Depth-First Search

/**
 * 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) {
        if (root == nullptr) {
            return 0;
        }

        int leftDepth = maxDepth(root->left);
        int rightDepth = maxDepth(root->right);

        return 1 + std::max(leftDepth, rightDepth);
    }
};

Code Explanation

Function Signature

int maxDepth(TreeNode* root)

The function receives a pointer to the root of the current tree or subtree and returns its maximum depth as an integer.

Null-Node Check

if (root == nullptr) {
    return 0;
}

A null pointer represents an empty tree. Since there is no node to count, its depth is 0.

This condition is essential because it stops the recursive calls after the algorithm moves past a leaf.

Calculate Both Subtree Depths

int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);

The function asks the left and right subtrees to calculate their own maximum depths.

The recursion continues until it reaches null pointers. It then begins returning results from the bottom of the tree toward the root.

Return the Current Depth

return 1 + std::max(leftDepth, rightDepth);

std::max selects the deeper subtree. Adding 1 counts the current node.

Walkthrough

Consider the first example:

root = [3,9,20,null,null,15,7]

The tree is:

        3
       / \
      9   20
         /  \
        15   7

The recursive calls reach the leaves before calculating the final answer.

Leaf Node 9

Both children of node 9 are null:

left depth  = 0
right depth = 0

Therefore:

depth of node 9 = 1 + max(0, 0) = 1

Leaf Node 15

Both children are null:

depth of node 15 = 1 + max(0, 0) = 1

Leaf Node 7

Both children are null:

depth of node 7 = 1 + max(0, 0) = 1

Node 20

The left and right subtree depths are both 1:

depth of node 20 = 1 + max(1, 1) = 2

Root Node 3

The left subtree has depth 1, and the right subtree has depth 2:

depth of node 3 = 1 + max(1, 2) = 3

The function returns 3.

Common Mistakes

Returning 1 for a Null Node

A null node contains no value and should contribute zero depth:

if (root == nullptr) {
    return 0;
}

Returning 1 would make every result too large.

Forgetting to Count the Current Node

The subtree result alone does not include the current node. The final expression must add 1:

return 1 + std::max(leftDepth, rightDepth);

Adding Both Subtree Depths

This problem asks for one longest root-to-leaf path. It does not ask for the total number of nodes in both branches.

Incorrect:

return 1 + leftDepth + rightDepth;

Correct:

return 1 + std::max(leftDepth, rightDepth);

Using the Smaller Subtree

The problem asks for the maximum depth, so the algorithm must select the larger subtree depth rather than the smaller one.

Confusing Node Values with Tree Depth

Values such as 3, 9, or 20 do not determine depth. Depth depends only on how nodes are connected.

Reporting Constant Auxiliary Space

The implementation does not use an explicit stack, but recursion uses the program's call stack. Its auxiliary space is O(h), not O(1).

Key Takeaways

• A binary tree is recursive because each child is the root of another binary tree.
• The maximum depth of a non-empty tree is one plus the greater depth of its left and right subtrees.
• A null tree has depth 0, which provides the recursion's base case.
• Recursive DFS visits every node once, giving O(n) time complexity.
• The recursive call stack uses O(h) auxiliary space and may reach O(n) for a skewed tree.