Maximum Depth of Binary Tree

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))

Watch the recursion stack: frames pile up on the way down to the leaves, then each frame pops with a concrete depth that its parent combines with the other child.

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.

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.