Maximum Depth of a Binary Tree – LeetCode75 Python Solution Explained

The Maximum Depth of a Binary Tree problem also known as LeetCode75 is one of the foundational challenges for anyone learning data structures and algorithms. Understanding how to determine the depth of a binary tree not only prepares you for technical interviews but also improves your problem-solving skills with recursive data structures.

In this blog, we will explain the problem, provide step-by-step Python solutions and break down the logic with code snippets at each stage. Additionally, we’ll cover time and space complexity, common edge cases and real-world applications of maximum depth in computing.

Problem Statement

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

Definition:
The maximum depth is defined as the number of nodes along the longest path from the root node down to the farthest leaf node.

Example 1

Input:

Output:

Explanation:
The longest path from the root to a leaf is either 3 → 20 → 15 or 3 → 20 → 7, so the maximum depth is 3.

Example 2

Input:

root = [1, null, 2]

Output:

Explanation:
The root has only one right child, so the depth of the tree is 2.

Understanding the Problem

A binary tree node contains a value and pointers to its left and right children. The challenge is to traverse the entire tree and determine the longest path from root to leaf.

Key points to understand:

Each node has a val, left, and right.
The maximum depth corresponds to the height of the tree.
This problem can be efficiently solved using recursion (depth-first search) or iterative approaches using stacks or queues (DFS/BFS).

Recursive Python Solution

Here’s a complete Python solution using recursion:

from typing import Optional

# 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:
        def dfs(node, depth):
            if not node:
                return depth
            return max(dfs(node.left, depth + 1), dfs(node.right, depth + 1))
        
        return dfs(root, 0)

This solution uses a helper function dfs to traverse the tree recursively and calculate the depth.

Step-by-Step Explanation with Code

Step 1: Base Condition

The base condition stops recursion at leaf nodes or empty subtrees.

if not node:
    return depth

If the current node is None, we return the current depth. This ensures that we do not continue traversing beyond leaf nodes.

Step 2: Recursively Traverse Left and Right Subtrees

We recursively call the dfs function for both the left and right child, incrementing the depth by 1 at each level.

left_depth = dfs(node.left, depth + 1)
right_depth = dfs(node.right, depth + 1)

This allows us to explore every path in the tree.

Step 3: Compute Maximum Depth

After computing the depth of the left and right subtrees, we take the maximum to determine the longest path from the root to any leaf.

return max(left_depth, right_depth)

This ensures that the deepest path is returned for each recursive call.

Step 4: Initiate DFS from Root

We start recursion from the root node with an initial depth of 0:

return dfs(root, 0)

The dfs function will return the maximum depth of the binary tree after exploring all paths.

Time and Space Complexity

Time Complexity: O(n)

Every node is visited exactly once, where n is the number of nodes in the tree.

Space Complexity: O(h)

h is the height of the tree, representing the recursion stack.
In the worst case (skewed tree), h = n.
In a balanced tree, h = log(n).

Edge Cases

Empty Tree → Return 0.

if not root:
    return 0

Single Node Tree → Depth is 1.
Skewed Tree → Maximum depth equals the number of nodes.

Iterative BFS Approach

You can also solve this problem using a queue and BFS to traverse level by level:

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
            for _ in range(len(queue)):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return depth

This approach is level-order traversal and avoids recursion which can be helpful in environments with recursion limits.

Real-World Applications

Parsing Nested Structures: XML, JSON, or HTML trees.
Decision Trees in Machine Learning: Maximum depth controls overfitting.
Filesystem Hierarchies: Finding the deepest folder in a directory tree.
Network Routing: Analyzing the longest path in hierarchical network models.
Game Development: Computing moves or states in tree-like structures.

Conclusion

The Maximum Depth of a Binary Tree problem is a foundational exercise in recursion, depth-first traversal and tree algorithms. Mastering it strengthens your understanding of:

Recursive problem-solving
Tree traversal techniques (DFS and BFS)
Complexity analysis
Edge-case handling

By practicing this problem, you also prepare for advanced binary tree questions such as balanced tree checks, diameter calculation and lowest common ancestor problems.

References

Programiz – Binary Tree in Python

Wikipedia – Binary Tree

LeetCode 104 – Maximum Depth of Binary Tree