What pattern does Maximum Depth of Binary Tree use?

The Pattern: DFS (Post-Order Traversal for Tree Depth) The Heuristic: When computing a property that depends on child nodes in a tree, use post-order DFS to first gather child results before combining them at the parent, enabling clean recursive definitions.

Maximum Depth of Binary Tree — DFS

Q: What is the time complexity of Maximum Depth of Binary Tree?

O(n). Each node is visited exactly once in the recursive traversal, resulting in linear time proportional to the number of nodes.

Problem

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 the farthest leaf node.

The number of nodes in the tree is in the range [0, 10⁴]
−100 ≤ Node.val ≤ 100

Example

Input: root = [3,9,20,null,null,15,7]

Output: 3

Starting at the root node with value 3, the algorithm recursively explores the left subtree rooted at 9 and the right subtree rooted at 20. The left subtree has depth 1 (node 9 is a leaf), while the right subtree has depth 2 (nodes 20 -> 15 or 20 -> 7). The maximum depth is therefore 1 + max(1, 2) = 3. The critical moment is the recursive calls returning depths for left and right subtrees, allowing the algorithm to combine these results to compute the overall maximum depth.

Approach

Straightforward Solution

A brute-force approach might attempt to traverse all paths and track the maximum length explicitly, but this would be more complex and less elegant. The straightforward recursive DFS directly encodes the definition of maximum depth.

Core Observation

The maximum depth of a binary tree is defined recursively: it is 1 plus the maximum depth of its left and right subtrees. This naturally suggests a depth-first traversal where each node's depth depends on its children's depths.

Path to Optimal

Preview

Recognizing that the problem's recursive structure matches the tree's definition leads to a simple DFS solution. The key insight is that the maximum depth at any node is 1 plus the maximum of the depths of its left and right children…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a recursive DFS function that returns 0 if the node is null (base case). Otherwise, recursively compute the maximum depth of the left and right subtrees, then return 1 plus the greater of these two depths…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each node is visited exactly once in the recursive traversal, resulting in linear time proportional to the number of nodes.

Space

O(h)

The recursion stack depth is proportional to the height h of the tree. In the worst case (skewed tree), this can be O(n), but for balanced trees, it is O(log n). This is auxiliary space excluding the input tree.

Solution

Python

1class Solution:
  def maxDepth(self, root: TreeNode) -> int:
      if not root:
          return 0
      
      left_depth = self.maxDepth(root.left)
      right_depth = self.maxDepth(root.right)
8
      return 1 + max(left_depth, right_depth)

Step-by-Step Solution

1

Return 0 for Null Nodes to Define Base Case Depth

3if not root:
4    return 0

Objective

To handle the base case of recursion by returning zero depth for null nodes.

Key Insight

The base case is essential to terminate recursion and correctly represent the depth of an empty subtree as zero. This allows the recursive calls to build up the depth count accurately from the leaves upward.

Interview Quick-Check

Core Logic

Returning 0 for null nodes defines the depth of an empty subtree, enabling the recursive formula to work correctly.

State & Boundaries

This base case prevents infinite recursion and marks the boundary condition for leaf nodes.

2

Recursively Compute Left and Right Subtree Depths

To explore the left and right subtrees and obtain their maximum depths.

3

Return 1 Plus Maximum of Left and Right Depths to Aggregate Result

To combine the depths of left and right subtrees and add one for the current node.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 9 Critical

return 1 + max(left_depth, right_depth)

Return one plus the maximum of left and right subtree depths.

This line embodies the recursive definition of maximum depth, combining child depths and adding one for the current node, which is the core logic that solves the problem.

Line 3 Critical

if not root:

Check if the current node is null to handle the base case.

This base case is critical to terminate recursion and correctly represent the depth of an empty subtree as zero, which is foundational for the recursive depth calculation.

Line 4 Critical

return 0

Return 0 for null nodes indicating zero depth.

Returning zero here ensures that leaf nodes compute their depth as 1 (1 + max(0,0)) and that recursion unwinds correctly with accurate depth values.

Full line-by-line criticality + rationale for all 5 lines available on Pro.

Test Your Understanding

Why does the recursive function return 0 for a null node, and how does this base case affect the overall depth calculation?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Maximum Depth of Binary Tree from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Maximum Depth of Binary Tree drill

or drill a free problem

1	`class Solution:`
2	`def maxDepth(self, root: TreeNode) -> int:`
3	`if not root:`
4	`return 0`
5
6	`left_depth = self.maxDepth(root.left)`
7	`right_depth = self.maxDepth(root.right)`
8
9	`return 1 + max(left_depth, right_depth)`