Skip to main content

🟩 Maximum Depth of Binary Tree (#104)

🔗 Problem Link​

📋 Problem Statement​

Given the root of a binary tree, return its maximum depth.

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

💡 Examples​

Example 1​

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

Example 2​

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

🔑 Key Insights & Approach​

Core Observation: Depth = 1 + max(left_depth, right_depth).

Why DFS Recursion?

  • Natural recursive structure
  • O(n) time, O(h) space
  • Simple and elegant

Approaches:

  1. Recursive DFS: O(n) time, O(h) space - optimal
  2. Iterative BFS: O(n) time, O(n) space
  3. Iterative DFS: O(n) time, O(h) space

Pattern: "Tree Height/Depth" recursive pattern.

🐍 Solution: Python​

Approach 1: Recursive DFS​

Time Complexity: O(n) | Space Complexity: O(h)

from typing import Optional

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 not root:
            return 0

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

        return 1 + max(left_depth, right_depth)

Approach 2: Iterative BFS (Level Order)​

Time Complexity: O(n) | Space Complexity: O(n)

from collections import deque
from typing import Optional

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        queue = deque([root])
        depth = 0

        while queue:
            depth += 1
            level_size = len(queue)

            for _ in range(level_size):
                node = queue.popleft()

                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

        return depth

🔵 Solution: Golang​

Approach: Recursive DFS​

Time Complexity: O(n) | Space Complexity: O(h)

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)

    return 1 + max(leftDepth, rightDepth)
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

📚 References​