Maximum Depth of Binary Tree

Google Interview Question

Problem Overview

Difficulty: Easy
LeetCode Pattern: Trees

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.

Input:
  1
 / \
2   3

Output:
· 2


Explanation:
· Both paths have depth 2.
· So max depth is 2.

Input:
  3
 / \
9   20
   /  \
  15   7
        \
        19    

Output:
· 4

Explanation:
· Longest path: 3→20→7→19
· So max depth is 4.

---

Step 1: Clarify Requirements

• Can the tree be empty?

  • Yes, return 0 in this case.

• What is depth of a single node?

  • 1 (just the root).

---

Step 2: Discuss Approaches

1/ Use DFS (Optimal ✅)

• Logic:

  • Base case:

    • node is None → return 0

  • Recurse left and right subtrees

  • Max depth = 1 + max(left, right)

• Big O:

  • Time: O(n)

  • Space: O(n)

---

2/ Use BFS (Optimal ✅)

• Logic:

  • Use a queue for level-order traversal

  • Count levels while traversing

  • Max depth = number of levels

• Big O:

  • Time: O(n)

  • Space: O(n)

---

Step 3: Write Code (Optimal)

Python

---

Java

---

C++

---

Step 4: Answer Follow-Ups

• What if the tree is very deep?

  • Recursion may hit stack overflow.

  • Use iterative BFS.

• How to do it for an n-ary tree?

  • Compute depth of all children.

  • Max Depth = 1 + max(all depths).