LeetCode 104 · Trees

Maximum Depth of Binary Tree, explained with a picture

How deep does the folder tree go?.

EasyTrees
▶ Watch it step by step

The problem

Return the maximum depth of a binary tree: the number of nodes on the longest path from the root down to a leaf.

Input:  [3, 9, 20, null, null, 15, 7]
Output: 3

Picture it

Picture a folder tree on a computer. To know how deep it goes, each folder asks its two subfolders “how deep are you?” and answers 1 + the deeper of the two. An empty spot answers 0. The answers bubble up from the bottom to the top folder.

How to recognise it

  • The input is a binary tree and the answer is one number about its shape.
  • The answer for a node can be built from the answers for its two children: depth of a tree = 1 + the deeper child. That is the signature of a bottom-up depth-first search (DFS: follow one branch to the bottom before trying the next).
  • "Depth" here counts nodes, not edges: a single node has depth 1, an empty tree 0.
  • Up to 10^4 nodes, so visit each node once.

Start with brute force

List every root-to-leaf path, then return the length of the longest one. It follows the definition word for word.

def max_depth_brute(root):
    paths = []
    def walk(node, path):
        if not node:
            return
        path = path + [node.val]          # copy of the path so far
        if not node.left and not node.right:
            paths.append(path)
        walk(node.left, path)
        walk(node.right, path)
    walk(root, [])
    return max((len(p) for p in paths), default=0)

Every node copies the path above it, so time is O(n · h), where h is the height. On a chain of 10^4 nodes that is about 5 × 10^7 copied items, and the stored paths can take O(n · h) memory too. All of that work is only used to read off a length.

From brute force to the idea

  1. Find the waste. We store whole paths but only need their lengths, and we only need the longest one.
  2. Ask the children instead. The longest path from a node down is the node itself plus the longest path in whichever subtree is deeper. So depth(node) = 1 + max(depth(left), depth(right)).
  3. Pick the base case. An empty spot has depth 0. A leaf then gets 1 + max(0, 0) = 1, which is correct with no special case for leaves.
  4. Return numbers, not lists. Each call returns one integer, so nothing is copied.

This is the key idea: a tree's depth is 1 plus the deeper child's depth, computed bottom-up in one DFS.

The key idea

depth(node) = 1 + max(depth(left), depth(right)). O(n).

Python solution

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

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n · h): each node copies the path above it (O(n²) for a chain)O(n · h): the stored paths
Recursive depth (shown code)O(n): each node is visited once and does O(1) workO(h): one stack frame per level, h = n for a chain

Edge cases

  • Empty tree: returns 0.
  • Single node: returns 1.
  • Chain (every node has one child): returns n; this is the deepest possible tree.
  • Very deep tree: a chain of about 1,000 nodes hits Python's default recursion limit and raises RecursionError, and LeetCode allows up to 10^4 nodes. For full safety use a level-by-level breadth-first search (BFS) and count the levels, or an explicit stack of (node, depth) pairs.

Common mistakes

  • Returning 1 for an empty tree, or counting edges instead of nodes, which is off by one.
  • Adding the two children's depths instead of taking the larger one; that measures a path through the node (the diameter idea), not depth.
  • Reusing this exact code for minimum depth by changing max to min: an empty child then counts as depth 0, so a node with one child looks like a leaf.
Your turn: minimum depth

Return the minimum depth (LeetCode 111): the number of nodes on the shortest path from the root down to a leaf. For [1, null, 2] the answer is 2, not 1, because the root is not a leaf. Describe your approach, then write it if you like.

Compare with our answer

Keep the bottom-up shape, but an empty child is not a leaf, so it must not win the min. If one child is missing, the path must go through the other child.

def min_depth(root):
    if not root:
        return 0
    if not root.left:
        return 1 + min_depth(root.right)
    if not root.right:
        return 1 + min_depth(root.left)
    return 1 + min(min_depth(root.left), min_depth(root.right))

Time O(n), space O(h). A BFS that stops at the first leaf it meets is also good, and it can finish early on a wide tree.

A strong answer mentions: why a missing child cannot count as depth 0, the one-child cases, and that a BFS can stop at the first leaf.

Check what stuck

1. You must find how many levels a company org chart has, where each person can have many reports. Which approach fits best?

2. Why is the shown solution O(n) time?

3. A learner turns the shown code into minimum depth by changing max to min. Which input now gets a wrong answer?

Score 60% or more and the lesson is marked complete.