TIC
The Interns Company

Maximum Depth of Binary Tree

EasyAcceptance: 70.1%
TreeDepth-First SearchBreadth-First SearchBinary Tree

Problem Statement

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

Constraints:

  • The number of nodes in the tree is in the range [0, 10^4]
  • -100 <= Node.val <= 100

Input Format:

  • The root of a binary tree

Output Format:

  • Return the maximum depth of the binary tree

Examples:

Example 1:

Input:

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

Output:

3

Explanation:

The binary tree has a depth of 3, with the root at depth 1, the second level at depth 2 (nodes 9 and 20), and the third level at depth 3 (nodes 15 and 7).

Example 2:

Input:

root = [1,null,2]

Output:

2

Explanation:

The binary tree has a depth of 2, with the root at depth 1 and node 2 at depth 2.

Example 3:

Input:

root = []

Output:

0

Explanation:

An empty tree has a depth of 0.

Example 4:

Input:

root = [1]

Output:

1

Explanation:

A tree with only the root node has a depth of 1.

Solutions

Recursive DFS Approach

Time: O(n)
Space: O(h)

Use recursion to compute the maximum depth by finding the maximum depth of the left and right subtrees and adding 1.

Iterative BFS Approach

Time: O(n)
Space: O(n)

Use a queue to perform level-order traversal and count the number of levels.

Iterative DFS Approach

Time: O(n)
Space: O(h)

Use a stack to perform depth-first traversal and keep track of the maximum depth.

Algorithm Walkthrough

Example input: nums = []

Step-by-step execution:

  1. Check if root is null: false
  2. Recursively call maxDepth on left subtree (node 9):
  3. Check if node 9 is null: false
  4. Recursively call maxDepth on its left child: null, return 0
  5. Recursively call maxDepth on its right child: null, return 0
  6. Return max(0, 0) + 1 = 1 for node 9
  7. Recursively call maxDepth on right subtree (node 20):
  8. Check if node 20 is null: false
  9. Recursively call maxDepth on its left child (node 15):
  10. Check if node 15 is null: false
  11. Both left and right children are null: return 1 for node 15
  12. Recursively call maxDepth on its right child (node 7):
  13. Check if node 7 is null: false
  14. Both left and right children are null: return 1 for node 7
  15. Return max(1, 1) + 1 = 2 for node 20
  16. Return max(1, 2) + 1 = 3 for the root

Hints

Hint 1
Think of using recursion to solve this problem. What is the maximum depth of an empty tree?
Hint 2
The depth of a node is the maximum of the depths of its left and right children, plus 1.
Hint 3
You can also solve this iteratively using BFS or DFS with a queue or stack.

Video Tutorial

Maximum Depth of Binary Tree - Recursive Approach

YouTube•Learn the Maximum Depth of Binary Tree solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize the recursive calls on the binary tree, showing the depth calculated at each step.

Key visualization elements:

  • current node
  • max depth so far
  • left subtree depth
  • right subtree depth

Asked By

AmazonGoogleMicrosoftAppleFacebookAdobeBloomberg

Implementation Notes

This is a fundamental binary tree problem that introduces depth-first traversal and recursive tree algorithms. It's often used as a stepping stone for more complex tree problems.