max-depth-binary-tree

---
id: max-depth-binary-tree
title: Maximum Depth of Binary Tree
slug: /problems/max-depth-binary-tree
difficulty: Easy
tags: [tree, binary-tree, recursion]
leetcode: https://leetcode.com/problems/maximum-depth-of-binary-tree/
---

# Maximum Depth of Binary Tree

Given a binary tree, return its maximum depth.
Note: the maximum depth is defined as the number of nodes along the longest path from root node to leaf node.

## Example(s)

**Example 1:**

Tree: 9 /
1 2 Output: 2

**Example 2:**

Tree: 5 /
1 29 /
4 13 Output: 3

## Solution

import Tabs from '@theme/Tabs';
import TabItem from '@theme/TabItem';

<Tabs>
<TabItem value="javascript" label="JavaScript Solution" default>

<CodeRunner
  language="javascript"
  title="JavaScript Maximum Depth Solution"
  code={`
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

/**
 * Find the maximum depth of a binary tree
 * @param {TreeNode} root - Root of the binary tree
 * @return {number} - Maximum depth
 */
function maxDepth(root) {
  if (!root) return 0;
  
  const leftDepth = maxDepth(root.left);
  const rightDepth = maxDepth(root.right);
  
  return Math.max(leftDepth, rightDepth) + 1;
}

// Test case 1: [9,1,2]
const tree1 = new TreeNode(9);
tree1.left = new TreeNode(1);
tree1.right = new TreeNode(2);

// Test case 2: [5,1,29,null,null,4,13]
const tree2 = new TreeNode(5);
tree2.left = new TreeNode(1);
tree2.right = new TreeNode(29);
tree2.right.left = new TreeNode(4);
tree2.right.right = new TreeNode(13);

// Test cases
console.log(maxDepth(tree1)); // 2
console.log(maxDepth(tree2)); // 3
console.log(maxDepth(null)); // 0
`}
/>

</TabItem>
<TabItem value="python" label="Python Solution">

<CodeRunner
  language="python"
  title="Python Maximum Depth Solution"
  code={`
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

def max_depth(root: Optional[TreeNode]) -> int:
    """
    Find the maximum depth of a binary tree
    
    Args:
        root: Root of the binary tree
        
    Returns:
        int: Maximum depth
    """
    if not root:
        return 0
    
    left_depth = max_depth(root.left)
    right_depth = max_depth(root.right)
    
    return max(left_depth, right_depth) + 1

# Test case 1: [9,1,2]
tree1 = TreeNode(9)
tree1.left = TreeNode(1)
tree1.right = TreeNode(2)

# Test case 2: [5,1,29,null,null,4,13]
tree2 = TreeNode(5)
tree2.left = TreeNode(1)
tree2.right = TreeNode(29)
tree2.right.left = TreeNode(4)
tree2.right.right = TreeNode(13)

# Test cases
print(max_depth(tree1))  # 2
print(max_depth(tree2))  # 3
print(max_depth(None))  # 0
`}
/>

</TabItem>
</Tabs>

## Complexity

- **Time Complexity:** O(n) - Where n is the number of nodes in the tree
- **Space Complexity:** O(h) - Where h is the height of the tree (recursion stack)

## Approach

The solution uses a **recursive approach**:

1. **Base case** handles empty tree by returning 0
2. **Recursive calls** find depth of left and right subtrees
3. **Return maximum** of left and right depths plus 1 for current node
4. **Height calculation** adds 1 for each node along the path

## Key Insights

- **Recursive approach** simplifies finding the maximum depth by comparing subtrees
- **Base case** handles empty tree by returning 0
- **Edge cases** include single-node tree and unbalanced trees
- **O(n) time** is optimal as all nodes may need to be visited to find the deepest path
- **Depth calculation** adds 1 for each node along the path from root to leaf