Compile Ready
Module 2 · DFS Traversals

Maximum Depth of Binary Tree

EasyProblem 4 of 24 8 min read ~15 min to solve LeetCode
TreeDFSPostorderRecursionSubtree Aggregation
Asked atMicrosoftAmazonGoogleMetaAppleBloomberg

Problem Statement

Given the root of a binary tree, return its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to any leaf node.

Input

The root pointer of a binary tree, or null for an empty tree.

Output

An integer representing the maximum number of nodes on any root-to-leaf path.

Constraints

  • •0 <= number of nodes <= 10000
  • •-100 <= Node.val <= 100

Examples

Example 1

Input: 
root = [3,9,20,null,null,15,7]
Output: 3
Explanation: The longest paths are **3 -> 20 -> 15** and **3 -> 20 -> 7**, each with three nodes.

Example 2

Input: 
root = [1,null,2]
Output: 2
Explanation: The longest path is **1 -> 2**, which contains two nodes.

Example 3

Input: 
root = []
Output: 0
Explanation: An empty tree has depth **0**.

Learning Objectives

  • Recognise maximum depth as postorder subtree aggregation.
  • Use **null -> 0** as the base case.
  • Combine child depths with **1 + max(left, right)**.
  • Distinguish counting nodes from counting edges.

Intuition

Pattern Recognition

The signal is maximum depth, height, or longest downward root-to-leaf path. This is a traversal where visiting means computing and returning a value for the current subtree, not appending to a list.

A node cannot know its own answer until it knows the best answer from both children. That makes the order postorder: get the left depth, get the right depth, then return 1 + max(left, right). The common trap is returning 1 for null, which overcounts missing children.

Common mistakes

  • ×Returning **1** for a **null** child instead of **0**.
  • ×Taking **min(left, right)** instead of **max(left, right)**.
  • ×Counting edges when the problem asks for nodes on the path.
  • ×Using a global variable even though the return value already carries the depth.

Algorithm Explanation

Key idea

Maximum depth introduces subtree aggregation. A null subtree contributes 0. A real node asks both children for their maximum depths and returns 1 + max(leftDepth, rightDepth), where 1 counts the current node.

Recursion walkthrough

Use [3,9,20,null,null,15,7]. Root 3 first asks left child 9. Node 9 sees two null children, gets depths 0 and 0, and returns 1. Then 3 asks right child 20. Node 20 asks 15 and 7; both leaves return 1 for the same reason. Node 20 returns 1 + max(1, 1) = 2. Finally 3 combines left depth 1 and right depth 2, returning 1 + max(1, 2) = 3. This is postorder because every parent returns after its children.

Algorithm

  1. If root is null, return 0.
  2. Recursively compute leftDepth from root.left.
  3. Recursively compute rightDepth from root.right.
  4. Return 1 + max(leftDepth, rightDepth).
  5. The value returned by the original root is the maximum depth.

Solutions

Solution: Postorder recursive depth aggregation

When to prefer this:

Use this as the default solution. It mirrors the definition of maximum depth and sets up harder height-based problems.

Treat each subtree as the same problem. A null subtree returns 0. A non-null node returns one plus the larger depth returned by its two children.

Step-by-step

  1. If root is null, return 0.
  2. Compute leftDepth by calling the function on root.left.
  3. Compute rightDepth by calling the function on root.right.
  4. Choose the larger child depth.
  5. Return 1 + max(leftDepth, rightDepth).
Time

O(n)

Space

O(h)

Every node performs one constant-time combine; the recursion stack is O(h), which becomes O(n) for a skewed tree.

Java implementation

Loading…

Dry Run

Sample input

root = [3,9,20,null,null,15,7]. Track postorder returns from leaves up to the root.

nodeleft depthright depthreturned depth
9001
15001
7001
20112
3123

Leaves return 1 because they count themselves above two null depths. The root chooses the deeper right subtree and returns 3.

Interview Tips

Call this a postorder aggregation, not just a traversal. The child calls return complete subtree answers, and the parent combines them. Be precise about null -> 0 and about counting nodes, not edges; that prevents the common off-by-one mistakes.

Likely follow-ups

  • How would minimum depth differ when one child is missing?
  • How would you check whether the tree is height-balanced?
  • How would you compute the diameter using returned child depths?
  • Can you compute maximum depth with BFS level order?

Similar Problems

Binary Tree Postorder Traversal
EasyUses the same children-before-parent order.
Balanced Binary Tree
EasyAlso returns subtree heights while checking a condition.
Diameter of Binary Tree
EasyUses child depths to update a longest path.
Binary Tree Level Order Traversal
MediumA BFS alternative can count levels instead of using recursion.

Key Takeaways

  • Maximum depth is postorder subtree aggregation.
  • The base case is **null -> 0**.
  • Each node returns **1 + max(leftDepth, rightDepth)**.
  • The same combine template powers balance and diameter problems.
Reusable template: Postorder aggregation: collect answers from the left and right subtrees, combine them locally, and return the subtree answer upward.