Maximum Depth of Binary Tree

Difficulty: Easy

Problem

Given the root of a binary tree, work out how many levels it has. Concretely, count the nodes on the longest chain that starts at the root and ends at a leaf, and return that count.

Example

Input: root = [3,9,20,null,null,15,7]
Output: 3
Explanation: The deepest chains are 3 → 20 → 15 and 3 → 20 → 7, each passing through 3 nodes, so the depth is 3.

Brute-force approach

The first idea is to list every root-to-leaf path and keep the longest. On the example it writes 3-9, 3-20-15 and 3-20-7: 2 + 3 + 3 = 8 steps for 5 nodes. It is correct, but every path re-writes the nodes it shares with the others, so a tall comb-shaped tree (a spine with a short tooth at every step) of 101 nodes costs 1,376 steps, and in the worst case the cost grows like n squared. The recursion below visits each node once.

Steps

  1. Walk the tree and write down every root-to-leaf path
  2. Count the nodes on each path
  3. Return the largest count

Time complexity: O(n^2) steps in the worst case · Space complexity: O(n) for the current path, more if every path is stored

Trade-offs

  • Shared nodes are re-counted for every path: 8 steps for 5 nodes on the example, 1,376 for a comb of 101 nodes
  • Grows like n squared in the worst case, while the recursion does n node visits

Optimal approach

Key insight: The depth of any node = 1 + max(depth of left child, depth of right child). For null nodes, return 0.

Use recursive DFS to calculate depth. For each node, the depth equals 1 (for the current node) plus the maximum depth of its left and right subtrees.

Steps

  1. Base case: If node is null, return 0
  2. Recursively get the depth of the left subtree
  3. Recursively get the depth of the right subtree
  4. Return 1 + max(leftDepth, rightDepth)

Time complexity: O(n) · Space complexity: O(h) where h = the number of levels (O(log n) when balanced, O(n) for a chain)

Pseudocode

function maxDepth(root):
    if root is ____:
        return ____
    
    left_depth = maxDepth(____)
    right_depth = maxDepth(____)
    
    return ____ + max(left_depth, right_depth)

Hints

  • Base case: What do we return for an empty tree (null node)?
  • Recursive calls: We need depth of root.left and root.right
  • Return: Add 1 for the current node to the max of children
  • A node with one child is not a leaf: the empty side answers 0 and never wins the max, so the other side decides.
  • Count nodes, not lines: the chain 3, 20, 15 is 3 nodes, so the answer is 3.
  • Why 1 + max: the node adds itself (1) on top of the deeper of its two sides, and the empty tree is 0.

Complexity questions

What is the time complexity of this recursive solution?

O(n). We visit every node exactly once. With n nodes in the tree, the time complexity is O(n).

What is the space complexity (considering the call stack)?

O(log n) when the tree is balanced, O(n) for a chain. The space is determined by the recursion call stack depth, which equals the number of levels h. For a balanced tree it's O(log n), for a chain (like a linked list) it's O(n). ("Average" is not defined here: the height of a typical tree depends on how the trees are drawn.) Python also stops the recursion at about a thousand waiting calls, so a chain of 1,000 nodes raises RecursionError.

Check your understanding of Maximum Depth of Binary Tree

What is the maximum depth of a tree with only a root node (no children)?

1. A tree with only a root node has depth 1. The root itself counts as one node in the path.

What is the maximum depth of an empty tree (null root)?

0. An empty tree (null) has depth 0 because there are no nodes.

For a tree with level-order array [1, 2, 3, 4], what is the maximum depth? (Tree: 1 at root, 2 and 3 as children, 4 as left child of 2)

3. The tree is: 1 → 2 → 4 on the left path, which has 3 nodes. So the maximum depth is 3.

In a tree where the left subtree has depth 3 and the right subtree has depth 5, what is the maximum depth of the whole tree?

6. The maximum depth is the longest root-to-leaf path. The right subtree has depth 5, plus 1 for the root node itself = 6.

Related problems

Keep practising