Maximum Depth of Binary Tree

The problem

You are given the root of a binary tree. Return its maximum depth: the number of nodes on the longest path that starts at the root and goes down to a leaf. A leaf is a node with no children.

Trees in the examples are written level by level, from left to right. null marks a missing child.

Example 1

Input: root = [4, 2, 9, null, null, 6, 1, 3]

Output: 4

The longest path down is 4, 9, 6, 3. It has 4 nodes. The path to 2 has only 2.

Example 2

Input: root = [7, null, 8]

Output: 2

7 has one child, 8. The path 7, 8 has 2 nodes.

Example 3

Input: root = []

Output: 0

An empty tree has no nodes, so no levels.

Constraints

• The tree has n nodes, where 0 ≤ n ≤ 10,000.
• -100 ≤ Node.val ≤ 100

Clarifying questions

Do we count nodes or edges?

Nodes. A tree with only a root has depth 1, not 0.

What does an empty tree return?

0. This is also the base case of the recursion.

Is the tree balanced?

Not always. It can be a single chain of 10,000 nodes, so the depth can be 10,000.

Do the values matter?

No. Only the shape of the tree counts.

Spot the pattern

The depth of a tree depends only on the depths of its two subtrees. Each node can answer once its children have answered. That is a tree traversal where each subtree hands a number back to its parent, and the parent combines the two numbers.

Solutions

RecursionO(n)

Show all

There is only one approach worth showing. The deepest leaf could be anywhere, so every node must be seen, and this visits each one once.

Recursion O(n)

The idea

Ask each node one question: how many levels are there under you, counting yourself?

An empty spot answers 0. A real node asks its left child and its right child first. Then it takes the bigger of the two answers and adds 1 for itself. The root’s answer is the depth of the whole tree.

The answers travel up the tree. A leaf answers 1, its parent answers 2 or more, and so on up to the root.

Why it is correct: the longest path from a node goes through one of its two children. So it is 1 plus the longer of the two paths below, and that is exactly what the node returns.

Walkthrough

call stack top →

empty

1. def max_depth(node):
2. if node is None:
3. return 0
4. left_depth = max_depth(node.left)
5. right_depth = max_depth(node.right)
6. return 1 + max(left_depth, right_depth)

Ask the root: how many levels are there under you, you included? It cannot know yet. It must ask its children first. Under a finished node, d2 means its depth answer is 2.

← BackStep →Play1 / 11

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Recursion: a tree is one level deeper than its deeper subtree.
    // Every node is visited once, so n steps.
    public int maxDepth(TreeNode root) {
        // An empty tree has no levels.
        if (root == null) return 0;
        // Each subtree answers the same question for itself.
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        // This node adds one level on top of the deeper side.
        return 1 + Math.max(leftDepth, rightDepth);
    }
}

Big O

Time O(n)Space O(h)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   There is no loop. The work repeats through recursion, so we count the calls. Each call does a fixed job: one check for empty, two calls, one max and one add. That does not grow with the tree, so each call counts as 1 step.

   1. def max_depth(node):
   2. if node is None:
   3. return 0
   4. left_depth = max_depth(node.left)
   5. right_depth = max_depth(node.right)
   6. return 1 + max(left_depth, right_depth)

2. 2 Count the runs on Example 1

   Example 1 has 6 nodes, and each gets one call. The picture shows the order. Empty children get a call too, which returns 0 at once. Node 2 has 2 empty children, 6 has 1, 1 has 2 and 3 has 2.

   6 node calls + 7 empty calls = 13 calls.

   total calls

   6 nodes + 7 empty children = 13

3. 3 Write the count for any n

   Every node gets one call. A binary tree with n nodes has n + 1 empty child spots, and each gets a call.

   n + (n + 1) = 2n + 1 calls

   Check it with Example 1: 2 × 6 + 1 = 13.

4. 4 Keep only the part that grows fastest

   • Drop the + 1. One extra call does not change how the work grows.
   • Drop the 2. When n doubles, 2n doubles too. The constant does not change the growth.

   What is left is n.

   So the time is O(n).

5. S Space: count the extra memory the same way

   The code keeps only left_depth and right_depth in each call. But every call that has started and not returned waits on the call stack, the memory a program keeps for unfinished calls. The most that wait at once is the height h of the tree.

   In Example 1, h is 4: the calls for 4, 9, 6 and 3 wait together. A balanced tree has h about log n, but a chain has h = n. So the space is O(h), and O(n) in the worst case.

   call stack (one frame per level)

Very deep trees

Each recursive call waits until the calls below it finish. If the tree is one long line of 10,000 nodes, that is 10,000 calls waiting at once. The algorithm is still right, but every language limits how many calls can wait, so a very deep tree can crash with a "stack overflow". Here is how to raise the limit:

• Python: stops at 1,000 calls. The code above raises it with sys.setrecursionlimit.
• Java: run with java -Xss64m, or run the work in new Thread(null, task, "main", 64L << 20).
• C#: run the work in new Thread(task, 64 * 1024 * 1024).
• TypeScript (Node): run with node --stack-size=30000.
• Go: nothing to do. Its stack grows by itself.

Recursion is still the answer interviewers expect for trees. Mention the limit out loud: "for a very deep tree, I would raise the stack limit or keep my own stack in a loop."

Common mistake

Returning 0 for a leaf

A leaf is a real node, so it counts as one level. Only an empty spot returns 0. If a leaf returns 0, every answer comes out one too small.

Tested at the limits

2,000 random trees of 0 to 12 nodes, in every shape. The recursion gave the same depth every time as a simple check that walks the tree with its own stack.

Largest inputs	Result
10,000 nodes (the most allowed), balanced, so 14 levels deep. Recursion.	0.001 s, and under 0.01 MB of extra memory: only 14 calls wait at once.
10,000 nodes in one long line, so 10,000 levels deep. Recursion.	0.002 s, and about 1 MB of extra memory: 10,000 calls wait at once, one per level, which is the O(h) space.