104. Maximum Depth of Binary Tree

Easy · solved 2026-10-05 · Open on LeetCode

treebinary-treedfs

Time O(n) · Space O(h)

How to get there

Build a node's depth from its children's

1. Restate the answer. The depth is the number of nodes on the longest path from the root down to a leaf.

2. Measure [3, 9, 20, null, null, 15, 7] by hand and find where one pass gets stuck. The root-to-leaf paths are 3–9 with 2 nodes, and 3–20–15 and 3–20–7 with 3 each, so the depth is 3. But standing at the root, there is no telling which branch runs longest: each one has to be walked to its end.

3. Find what to remember. For each subtree, its depth. A tree’s depth is 1 for its root plus the depth of its deeper subtree, and an empty tree’s depth is 0. The question about the whole tree is the same question about each subtree, so it is a recursion.

4. Let the dependency pick the order. A node’s answer needs both its children’s answers first, so each call walks a whole subtree before it can return. That is depth-first search, in postorder: the node’s own work happens after both subtrees. The call stack holds the path from the root to the node being worked on.

5. Or carry the depth down instead. solution-1-top-down.py passes the depth so far to each child, and every empty child returns the depth it reached; the largest of those is the answer. It is the same walk, with the information flowing down as parameters instead of up as return values.

6. Check the cost. Every node is visited once: O(n) time. The call stack is as deep as the tree is tall, O(h), which is n for a tree that is one long chain.

The reusable recipe: when a node’s answer is built from its children’s answers, recurse into the children first and combine their results on the way back up.

Let the return value's meaning write the function

Code	Always means
`visit(node)` in `solution-2-bottom-up.py`	returns the depth of the subtree rooted at `node`: the nodes on its longest downward path
`visit(node, depth)` in `solution-1-top-down.py`	`depth` counts the nodes above `node`; returns the deepest count any path below it reaches
`(current, depth)` on the stack in `solution-3-stack.py`	`depth` counts the nodes from the root down to `current`; `best` is the largest depth popped so far

Each case of the bottom-up visit is the smallest answer that keeps its meaning true:

Case	What it means	Code
`node` is `None`	an empty subtree has no nodes	`return 0`
`node` exists	the node itself, plus the deeper of its two subtrees	`return 1 + max(self.visit(node.right), self.visit(node.left))`

maxDepth(root) is visit(root): the whole tree is the subtree rooted at the root, and an empty tree falls into the first case.

Neither version needs a visited set: each node is reached only from its parent, so no node is visited twice. The order of the two calls inside max doesn’t matter either; walking the right subtree first gives the same answer as the left.

The method carries over: write down what the function returns for any node, then the empty case and the combining step each follow from that meaning.

Alternatives compared

Approach	Time	Space	How it works
Top-down recursion (`solution-1-top-down.py`)	O(n)	O(h)	Pass the depth so far to each child; each empty child returns the depth it reached.
Bottom-up recursion (chosen, `solution-2-bottom-up.py`)	O(n)	O(h)	Each node returns 1 plus the larger of its children’s depths.
Explicit stack of (node, depth) pairs (`solution-3-stack.py`)	O(n)	O(h)	Iterative depth-first search: pop a pair, update the deepest depth seen, and push the children one level deeper.
Breadth-first search, counting levels	O(n)	O(w)	Take the tree one level at a time with a queue; the number of levels is the depth. w is the widest level.

Both recursions make one call per level, and Python stops at 1,000 calls by default: on a chain of 10,000 nodes, the largest tree the problem allows, both raised RecursionError when run locally. The explicit stack has no such limit: solution-3-stack.py returned 10,000 on the same chain.

The explicit stack has to carry what the recursion kept for free. A call knows its depth from its own parameter or return value, but a node popped off a stack carries nothing, so each entry is a (node, depth) pair and every child is pushed one level deeper than its parent.

solution-1-top-down.py

# 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
class Solution:
    def maxDepth(self, root: TreeNode | None) -> int:
        return self.visit(root, 0)

    def visit(self, node: TreeNode | None, depth: int) -> int:
        if node:
            return max(self.visit(node.right, depth+1), self.visit(node.left, depth+1))
        else:
            return depth

solution-2-bottom-up.py

# 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
class Solution:
    def maxDepth(self, root: TreeNode | None) -> int:
        return self.visit(root)

    def visit(self, node: TreeNode | None) -> int:
        if node:
            return 1 + max(self.visit(node.right), self.visit(node.left))
        else:
            return 0

solution-3-stack.py

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

        stack = [(root, 1)]
        best = 0
        while stack:
            current, depth = stack.pop()
            best = max(best, depth)
            if current.left:
                stack.append((current.left, depth+1))
            if current.right:
                stack.append((current.right, depth+1))

        return best

Notes

Write your approach, insights, and mistakes here. Any other file in this folder (e.g. solution.py, attempt-1.py) is rendered below as code.