LeetCode 104 - Maximum Depth of Binary Tree

The problem asks us to determine the maximum depth of a binary tree. A binary tree consists of nodes where each node can have up to two children, a left child and a right child.

leetcodeeasytreedepth-first-searchbreadth-first-searchbinary-tree

LeetCode Problem 104

Difficulty: 🟢 Easy
Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree

Solution

Problem Understanding

The problem asks us to determine the maximum depth of a binary tree. A binary tree consists of nodes where each node can have up to two children, a left child and a right child. The depth of a tree is defined as the number of nodes along the longest path from the root node down to the farthest leaf node.

In simpler terms, we need to find how many levels exist in the tree. Starting at the root node, we move downward through child nodes, and we want the length of the deepest possible path. A leaf node is a node with no children, so the maximum depth corresponds to the deepest leaf reachable from the root.

The input is the root of a binary tree. This root node represents the entry point to the entire tree structure. Each node contains a value and references to its left and right child nodes. The output is a single integer representing the maximum number of nodes encountered along the longest path from the root to a leaf.

The constraints tell us that the tree can contain anywhere from 0 to 10^4 nodes. Since the input size can become fairly large, we should avoid unnecessarily expensive operations. The node values themselves range between -100 and 100, but these values are irrelevant for solving the problem because depth depends only on structure, not node contents.

Several important edge cases stand out immediately. The tree may be empty (root = None), in which case the maximum depth is 0. The tree may contain only a single node, where the answer is 1. Another important case is a highly unbalanced tree, where nodes form essentially a linked list. In such situations, recursion depth may become large, but the algorithm must still correctly count the path length. The problem guarantees a valid binary tree structure, so we do not need to handle malformed input.

Approaches

Brute Force Approach

A brute-force way to think about this problem is to enumerate every root-to-leaf path and explicitly compute the length of each path, then return the maximum value. We could perform a traversal of the tree, record every complete path to a leaf, and compare their lengths afterward.

This approach is correct because every possible root-to-leaf path is explored, guaranteeing that the longest one will be found. However, it is unnecessarily expensive because we store full path information even though we only need the maximum depth. Maintaining all paths introduces avoidable overhead in both memory and implementation complexity.

Optimal Approach

The key observation is that the depth of a tree can be defined recursively.

For any node:

  • The maximum depth of its subtree equals:

1 + max(depth(left subtree), depth(right subtree))

This works because every path from the current node to a leaf must continue through either the left child or the right child. Therefore, if we already know the depth of both subtrees, we can determine the current node's depth by taking the larger one and adding one for the current node itself.

This naturally suggests a Depth-First Search (DFS) recursive solution. We recursively compute the depth of the left subtree and right subtree, then return the larger value plus one.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Traverses every node and stores root-to-leaf paths unnecessarily
Optimal O(n) O(h) DFS recursion computes depth directly, where h is tree height

Algorithm Walkthrough

We will use a recursive Depth-First Search strategy.

  1. Handle the base case for an empty node

If the current node is None, return 0. This represents an empty subtree having depth zero. This base case prevents infinite recursion and provides a stopping condition. 2. Recursively compute the left subtree depth

Call the same function on root.left. This gives the maximum depth reachable through the left child. 3. Recursively compute the right subtree depth

Call the function on root.right. This gives the maximum depth reachable through the right child. 4. Choose the deeper subtree

Compare the left and right subtree depths using max(). Since the longest path determines the answer, we only care about the deeper branch. 5. Include the current node

Add 1 to account for the current node itself and return the result. 6. Propagate the answer upward

Each recursive call returns its computed depth to its parent until the root finally receives the maximum tree depth.

Why it works

The algorithm works because of the recursive property of binary trees. Every subtree is itself a binary tree, meaning the same logic applies at every level. For any node, the maximum depth must equal one plus the larger depth of its children. Since recursion correctly computes subtree depths bottom-up, the root ultimately receives the maximum depth of the entire tree. The base case guarantees correctness for empty subtrees.

Python Solution

# 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:
        if root is None:
            return 0

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

        return 1 + max(left_depth, right_depth)

The implementation directly mirrors the recursive definition of tree depth.

The first condition checks whether the current node is None. If so, it returns 0, since an empty tree contributes no depth.

Next, the function recursively computes the depth of the left subtree and stores it in left_depth. It does the same for the right subtree in right_depth.

Finally, the function compares both subtree depths, selects the larger one, and adds 1 to include the current node. This value is returned upward through the recursive call stack until the root receives the final answer.

The code remains concise because the recursive relationship perfectly matches the problem definition.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }

    leftDepth := maxDepth(root.Left)
    rightDepth := maxDepth(root.Right)

    if leftDepth > rightDepth {
        return leftDepth + 1
    }

    return rightDepth + 1
}

The Go implementation follows exactly the same recursive structure as the Python version. The main difference is how nil is used instead of None for empty nodes.

Go does not provide a built-in max() function for integers, so we manually compare leftDepth and rightDepth with an if statement.

Since the problem constraints stay comfortably within standard integer limits, integer overflow is not a concern.

Worked Examples

Example 1

Input:

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

Tree structure:

        3
       / \
      9   20
         /  \
        15   7

We recursively compute depths from the bottom upward.

Node Left Depth Right Depth Result
9 0 0 1
15 0 0 1
7 0 0 1
20 1 1 2
3 1 2 3

Step-by-step execution:

  1. Start at node 3.
  2. Recurse into left child 9.
  3. Node 9 has no children, so both recursive calls return 0.
  4. Node 9 returns 1 + max(0, 0) = 1.
  5. Recurse into node 20.
  6. Node 20 explores children 15 and 7.
  7. Both leaf nodes return 1.
  8. Node 20 returns 1 + max(1, 1) = 2.
  9. Root node 3 returns 1 + max(1, 2) = 3.

Output:

3

Example 2

Input:

root = [1,null,2]

Tree structure:

    1
     \
      2
Node Left Depth Right Depth Result
2 0 0 1
1 0 1 2

Step-by-step execution:

  1. Start at node 1.
  2. Left child is None, return 0.
  3. Recurse into right child 2.
  4. Node 2 is a leaf node, so it returns 1.
  5. Node 1 returns 1 + max(0, 1) = 2.

Output:

2

Complexity Analysis

Measure Complexity Explanation
Time O(n) Every node is visited exactly once
Space O(h) Recursive call stack stores up to tree height h

The time complexity is O(n) because every node in the tree is processed exactly once. At each node, only constant-time work is performed, namely recursive calls and a comparison.

The space complexity is O(h), where h is the height of the tree. This comes from the recursion stack. In a balanced tree, h = O(log n), while in the worst case of a completely skewed tree, h = O(n).

Test Cases

# Definition for testing
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

solution = Solution()

# Example 1
root1 = TreeNode(
    3,
    TreeNode(9),
    TreeNode(20, TreeNode(15), TreeNode(7))
)
assert solution.maxDepth(root1) == 3  # balanced tree example

# Example 2
root2 = TreeNode(1, None, TreeNode(2))
assert solution.maxDepth(root2) == 2  # right-skewed tree

# Empty tree
assert solution.maxDepth(None) == 0  # no nodes

# Single node
root3 = TreeNode(1)
assert solution.maxDepth(root3) == 1  # smallest non-empty tree

# Left-skewed tree
root4 = TreeNode(
    1,
    TreeNode(
        2,
        TreeNode(
            3,
            TreeNode(4)
        )
    )
)
assert solution.maxDepth(root4) == 4  # deep left chain

# Right-skewed tree
root5 = TreeNode(
    1,
    None,
    TreeNode(
        2,
        None,
        TreeNode(3)
    )
)
assert solution.maxDepth(root5) == 3  # deep right chain

# Perfect binary tree
root6 = TreeNode(
    1,
    TreeNode(2, TreeNode(4), TreeNode(5)),
    TreeNode(3, TreeNode(6), TreeNode(7))
)
assert solution.maxDepth(root6) == 3  # balanced full tree

# Uneven tree
root7 = TreeNode(
    1,
    TreeNode(2),
    TreeNode(3, TreeNode(4, TreeNode(5)), None)
)
assert solution.maxDepth(root7) == 4  # deeper subtree determines answer
Test Why
[3,9,20,null,null,15,7] Validates the main example
[1,null,2] Verifies right-skewed structure
[] Tests empty tree handling
[1] Validates single-node case
Left-skewed tree Ensures recursion handles deep left branches
Right-skewed tree Ensures recursion handles deep right branches
Perfect binary tree Verifies balanced tree behavior
Uneven tree Confirms algorithm selects deeper subtree

Edge Cases

Empty Tree

An empty tree occurs when root is None. This can easily cause errors if code assumes a node always exists and immediately tries to access child pointers. Our implementation handles this safely with the base case:

if root is None:
    return 0

This guarantees an empty tree correctly returns depth 0.

Single Node Tree

A tree containing only one node is another common edge case. Since the root is also a leaf, the maximum depth should be 1. Some implementations accidentally return 0 if they count edges instead of nodes. Our implementation correctly returns 1 because it adds one for the current node.

Highly Skewed Tree

A tree where every node has only one child behaves like a linked list. For example:

1
 \
  2
   \
    3

This case is important because recursion depth becomes equal to the number of nodes. A poorly designed implementation might incorrectly stop early or fail to explore one side consistently. Our recursive DFS correctly traverses every node and accumulates the proper depth by repeatedly adding one at each level.