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

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)

Pseudocode

function maxDepth(root):
    if root is ____:
        return ____
    
    leftDepth = maxDepth(____)
    rightDepth = maxDepth(____)
    
    return ____ + max(leftDepth, rightDepth)

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

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) average, O(n) worst. The space is determined by the recursion call stack depth, which equals the height of the tree. For a balanced tree it's O(log n), for a skewed tree (like a linked list) it's O(n).

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