Maximum Depth of Binary Tree

The depth of a tree is 1 plus the deeper of its two subtrees’ depths — a tiny recursive definition that maps directly onto code. Both solutions below are O(n), they just differ in whether recursion or an explicit queue tracks progress.

Recursive (DFS)

Time O(n)Space O(h)

An empty tree has depth 0. Otherwise, the depth is 1 (for the current node) plus whichever child subtree is deeper.

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: TreeNode | None) -> int:
        if root is None:
            return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

Tracing root = [3,9,20,null,null,15,7] — the recursion bottoms out at the leaves first, then depths combine on the way back up:

1 / 4

comparingseenresult

Node 9 is a leaf: both children are None, so it returns depth 1.

Complexity: every node is visited once and does O(1) work → O(n) time. Call stack depth tracks the tree’s height → O(h) space, which is O(log n) balanced but O(n) for a skewed tree.

Iterative (BFS level counting)

Time O(n)Space O(n)

Recursion depth is bounded by tree height, which risks a stack overflow on a very unbalanced tree. A level-order walk sidesteps that: process one full level of the queue at a time and increment a counter per level — the counter is the depth once the queue empties.

from collections import deque

class Solution:
    def maxDepth(self, root: TreeNode | None) -> int:
        if root is None:
            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

Why prefer this: still O(n) time, but space is bounded by the queue’s peak width rather than the tree’s height — no recursion limit to worry about. For a wide, shallow tree the queue can hold up to ~n/2 nodes, so worst-case space is still O(n); the win is robustness, not a better asymptotic bound.