Domain 1EasyCORE

Maximum Depth of Binary Tree

The problem asks us to find the maximum depth of a binary 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.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Tree#Depth-first Search#Recursion

104. Maximum Depth of Binary Tree

Model: qwen2.5-coder:14b
Topics: Tree,Depth-first Search,Recursion
FAANG asked: 1
Acceptance rate: 68.3%


Problem Breakdown

The problem asks us to find the maximum depth of a binary 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.

Inputs:

  • root: The root node of a binary tree.

Outputs:

  • An integer representing the maximum depth of the binary tree.

Implicit Constraints or Tricky Edge Cases:

  • If the tree is empty (root is None), the maximum depth should be 0.
  • A single-node tree has a maximum depth of 1.
  • The tree can have up to 10,000 nodes, so the solution should be efficient in terms of both time and space.

Intuition

A brute-force approach would involve traversing all paths from the root to the leaf nodes and keeping track of the longest path. However, this approach is inefficient because it requires visiting every node multiple times.

The key insight is to use a recursive approach to traverse the tree. By recursively calculating the maximum depth of the left and right subtrees, we can determine the maximum depth of the entire tree efficiently. This approach leverages the divide-and-conquer strategy, where we break down the problem into smaller subproblems (left and right subtrees) and combine their results.

Approach

  1. Base Case: If the root is None, return 0 because an empty tree has a depth of 0.
  2. Recursive Case: Recursively calculate the maximum depth of the left subtree (maxDepth(root.left)) and the right subtree (maxDepth(root.right)).
  3. The maximum depth of the current node is the greater of the depths of its left and right subtrees, plus one (to account for the current node itself).

Complexity Analysis

  • Time Complexity: O(n), where n is the number of nodes in the tree. Each node is visited once.
  • Space Complexity: O(h), where h is the height of the tree. This is due to the recursion stack, which can go as deep as the height of the tree.

Solution

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

def maxDepth(root: TreeNode) -> int:
    if root is None:
        return 0
    # Recursively find the depth of the left and right subtrees
    left_depth = maxDepth(root.left)
    right_depth = maxDepth(root.right)
    # The maximum depth is the greater of the two depths plus one for the current node
    return max(left_depth, right_depth) + 1

Edge Cases Handled

  • Empty Tree: If root is None, the function returns 0.
  • Single Node Tree: If the tree has only one node (root), the function returns 1.
  • Balanced and Unbalanced Trees: The solution works for both balanced and unbalanced trees, as it correctly calculates the depth based on the longest path from the root to a leaf.