104. Maximum Depth of Binary Tree (Easy)

Problem

Given the root of a binary tree, return its maximum depth, the number of nodes along the longest path from the root to a leaf.

Example

• root = [3,9,20,null,null,15,7] → 3
• root = [1,null,2] → 2

LeetCode 104 · Link · Easy

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Recursive DFS (canonical one-liner)

Depth of a node is 1 + max depth of its children.

Python

def max_depth(root):
    if not root:
        return 0                                           # L1: base case
    return 1 + max(max_depth(root.left), max_depth(root.right))  # L2: recurse both children

TypeScript

class TreeNode {
    val: number; left: TreeNode | null; right: TreeNode | null;
    constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val; this.left = left; this.right = right;
    }
}

function maxDepth(root: TreeNode | null): number {
    if (!root) return 0;                                              // L1: base case
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));  // L2: recurse both children
}

Go

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0                                                  // L1: base case
    }
    left := maxDepth(root.Left)
    right := maxDepth(root.Right)
    if left > right {
        return 1 + left                                           // L2: recurse both children
    }
    return 1 + right
}

Swift

final class Solution { func maxDepth(_ root: TreeNode?) -> Int { guard let root else { return 0 }; return 1 + max(maxDepth(root.left), maxDepth(root.right)) } }

Where the time goes, line by line

Variables: n = number of nodes in the tree, h = tree height, w = max tree width.

Line	Per-call cost	Times executed	Contribution
L1 (base case)	$O(1)$	n+1 null checks	$O(n)$
L2 (recurse + max)	$O(1)$ per node	n	$O(n)$ ← dominates (both lines tie)

Every node triggers exactly two recursive calls (left, right) and one max. No node is visited more than once because the recursion tree mirrors the tree structure.

Complexity

• Time: $O(n)$, driven by L2 visiting each node once.
• Space: $O(h)$ recursion.

Approach 2: BFS level count

Count levels with a queue.

Python

from collections import deque

def max_depth(root):
    if not root:
        return 0
    q = deque([root])   # L1: O(1) init
    depth = 0
    while q:
        depth += 1                      # L2: O(1) increment per level
        for _ in range(len(q)):
            node = q.popleft()          # L3: O(1) dequeue
            if node.left:
                q.append(node.left)     # L4: O(1) enqueue
            if node.right:
                q.append(node.right)    # L5: O(1) enqueue
    return depth

TypeScript

function maxDepth(root: TreeNode | null): number {
    if (!root) return 0;
    const q: TreeNode[] = [root];  // L1: O(1) init
    let depth = 0;
    while (q.length) {
        depth++;                              // L2: O(1) increment per level
        const levelSize = q.length;
        for (let i = 0; i < levelSize; i++) {
            const node = q.shift()!;         // L3: O(1) dequeue
            if (node.left) q.push(node.left);    // L4: O(1) enqueue
            if (node.right) q.push(node.right);  // L5: O(1) enqueue
        }
    }
    return depth;
}

Go

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    q := []*TreeNode{root}  // L1: O(1) init
    depth := 0
    for len(q) > 0 {
        depth++                              // L2: O(1) increment per level
        levelSize := len(q)
        for i := 0; i < levelSize; i++ {
            node := q[0]
            q = q[1:]                        // L3: O(1) dequeue
            if node.Left != nil {
                q = append(q, node.Left)     // L4: O(1) enqueue
            }
            if node.Right != nil {
                q = append(q, node.Right)    // L5: O(1) enqueue
            }
        }
    }
    return depth
}

Swift

final class Solution {
    func maxDepth(_ root: TreeNode?) -> Int { guard let root else { return 0 }; var queue = [root], read = 0, depth = 0; while read < queue.count { let end = queue.count; while read < end { let node = queue[read]; read += 1; if let left = node.left { queue.append(left) }; if let right = node.right { queue.append(right) } }; depth += 1 }; return depth }
}

Where the time goes, line by line

Variables: n = number of nodes in the tree, h = tree height, w = max tree width.

Line	Per-call cost	Times executed	Contribution
L2 (depth++)	$O(1)$	h levels	$O(h)$
L3 (dequeue)	$O(1)$	n	$O(n)$
L4/L5 (enqueue)	$O(1)$	n	$O(n)$ ← dominates

Complexity

• Time: $O(n)$.
• Space: $O(w)$.

Useful when recursion depth is a concern; also the starting point for level-order problems.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Iterative DFS carrying depth

Stack of (node, current_depth) pairs.

Python

def max_depth(root):
    if not root:
        return 0
    stack = [(root, 1)]   # L1: O(1) init with depth 1
    best = 0
    while stack:
        node, d = stack.pop()          # L2: O(1) pop
        best = max(best, d)            # L3: O(1) update best
        if node.left:
            stack.append((node.left, d + 1))   # L4: O(1) push
        if node.right:
            stack.append((node.right, d + 1))  # L5: O(1) push
    return best

Swift

final class Solution {
    func maxDepth(_ root: TreeNode?) -> Int { guard let root else { return 0 }; var stack: [(TreeNode, Int)] = [(root, 1)], best = 0; while let entry = stack.popLast() { best = max(best, entry.1); if let left = entry.0.left { stack.append((left, entry.1 + 1)) }; if let right = entry.0.right { stack.append((right, entry.1 + 1)) } }; return best }
}

Where the time goes, line by line

Variables: n = number of nodes in the tree, h = tree height, w = max tree width.

Line	Per-call cost	Times executed	Contribution
L2 (pop)	$O(1)$	n	$O(n)$
L3 (max)	$O(1)$	n	$O(n)$
L4/L5 (push)	$O(1)$	n	$O(n)$ ← dominates (all lines tie)

Complexity

• Time: $O(n)$.
• Space: $O(h)$.

Summary

Approach	Time	Space
Recursive DFS	$O(n)$	$O(h)$
BFS level count	$O(n)$	$O(w)$
Iterative DFS with depth	$O(n)$	$O(h)$

All optimal; the one-line recursion is the canonical answer.

Test cases

Python

from collections import deque

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

def build_tree(vals):
    if not vals: return None
    root = TreeNode(vals[0])
    q = [root]
    i = 1
    while q and i < len(vals):
        node = q.pop(0)
        if i < len(vals) and vals[i] is not None:
            node.left = TreeNode(vals[i])
            q.append(node.left)
        i += 1
        if i < len(vals) and vals[i] is not None:
            node.right = TreeNode(vals[i])
            q.append(node.right)
        i += 1
    return root

def max_depth(root):
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

def _run_tests():
    assert max_depth(build_tree([3, 9, 20, None, None, 15, 7])) == 3
    assert max_depth(build_tree([1, None, 2])) == 2
    assert max_depth(None) == 0
    assert max_depth(build_tree([1])) == 1
    # skewed tree of depth 4
    t = TreeNode(1, TreeNode(2, TreeNode(3, TreeNode(4))))
    assert max_depth(t) == 4
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

class TreeNode {
    val: number; left: TreeNode | null; right: TreeNode | null;
    constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val; this.left = left; this.right = right;
    }
}

function buildTree(vals: (number | null)[]): TreeNode | null {
    if (!vals.length) return null;
    const root = new TreeNode(vals[0] as number);
    const q: TreeNode[] = [root];
    let i = 1;
    while (q.length && i < vals.length) {
        const node = q.shift()!;
        if (i < vals.length && vals[i] !== null) { node.left = new TreeNode(vals[i] as number); q.push(node.left); }
        i++;
        if (i < vals.length && vals[i] !== null) { node.right = new TreeNode(vals[i] as number); q.push(node.right); }
        i++;
    }
    return root;
}

function maxDepth(root: TreeNode | null): number {
    if (!root) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

console.assert(maxDepth(buildTree([3, 9, 20, null, null, 15, 7])) === 3);
console.assert(maxDepth(buildTree([1, null, 2])) === 2);
console.assert(maxDepth(null) === 0);
console.assert(maxDepth(buildTree([1])) === 1);
const t = new TreeNode(1, new TreeNode(2, new TreeNode(3, new TreeNode(4))));
console.assert(maxDepth(t) === 4);
console.log("all tests pass");

Related data structures

• Binary Trees & BSTs, height computation
• Queues, BFS level count

Related concepts

• Recursion, self-similar problem-solving tactics for trees, divide-and-conquer, and search branches.
• Tree Traversal, recursive and iterative tactics for visiting tree nodes with path, depth, or structural state.