Maximum Depth of Binary Tree

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 downward to a leaf (a node with no children). An empty tree has depth 0 and a tree with only a root has depth 1.

Trees are written in level order: the root first, then each level from left to right, with null marking a missing child. For example, [4,2,7,null,null,6] is a root 4 with children 2 and 7, where 7 has a left child 6.

Example 1

Example 2

Example 3

Constraints

• The number of nodes is between 0 and 104.
• The depth of the tree is at most 500.
• -100 <= Node.val <= 100

Pattern Path · Trees: DFS · problem 83 of 169

Start simple

Enumerating every root-to-leaf path separately and measuring each is wasteful; a single traversal visits each node once in O(n).

The key idea

The depth of a tree is defined recursively: an empty tree has depth 0, and any other tree has depth 1 + max(depth(left), depth(right)), because the deepest path must go through the root and then continue into whichever subtree is deeper.

A recursive depth-first search implements this definition directly. Each call handles one node, so every node is visited exactly once. The recursion goes as deep as the tree is tall, so the call stack uses O(h) space, where h is the height: about log n for a balanced tree and up to n for a tree that is just a long chain.

An equally good iterative alternative is breadth-first search: process the tree one level at a time using a queue and count the levels. That avoids deep recursion entirely, which matters in languages with small stack limits when the tree can be very unbalanced.

Complexity

• Time: O(n)
• Space: O(h) for the recursion, where h is the tree height

Python

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

JavaScript

var maxDepth = function(root) {
  if (root === null) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
};

What the interviewer is checking

It is the canonical first tree recursion: the interviewer checks that you trust the recursive definition, handle the empty tree as the base case, and can discuss recursion depth versus an iterative BFS.

Mistakes to avoid

• Returning 1 for an empty tree, or forgetting the null check entirely.
• Counting edges instead of nodes (off by one).
• Using a recursive solution on a very deep, chain-like tree without considering stack overflow.

Follow-ups to expect

• Find the minimum depth instead. (Careful with nodes having one child.)
• Do it without recursion. (BFS by levels, or DFS with explicit stack.)
• Check whether the tree is height-balanced. (Return height, -1 if unbalanced.)

In real software

Measuring the nesting depth of a DOM, a JSON document, a directory tree or an expression tree uses the same computation, often to enforce limits against overly deep input.

Practice next