How to Solve: Maximum Depth of a Binary Tree

How to Solve: Maximum Depth of a Binary Tree

(A Complete FAANG-Level Interview Guide)

? Introduction

"This problem is the litmus test for recursion mastery—FAANG interviewers use it to separate candidates who ‘kinda know trees’ from those who can write clean, efficient recursive logic under pressure. Nail it, and you prove you can handle any tree-based problem."

? WHAT YOU NEED TO KNOW FIRST

Before diving in, ensure you understand: 1. Binary Tree Basics – Structure (nodes, left/right children, root), traversal (DFS/BFS). 2. Recursion – Base case, recursive case, call stack, and how recursion translates to iterative solutions. 3. Time/Space Complexity – Big-O notation for trees (e.g., O(n) for visiting all nodes).

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

(Repeatable mental checklist for any "tree depth" problem.)

1. Clarify the Problem
2. Ask: "Is the depth defined as the number of nodes or edges along the longest path?" (Standard: edges = nodes - 1.)

3. Confirm: "What should I return for an empty tree?" (Usually 0.)

4. Choose the Right Technique

5. Recursive DFS → Default for simplicity.
6. Iterative DFS/BFS → If recursion depth is a concern (e.g., 10,000+ nodes).

7. BFS → If the problem involves levels (e.g., "maximum depth of a level with X property").

8. Write the Base Case

9. For recursion: if not root: return 0.

10. For BFS: if not root: return 0 (initialize queue with root and depth=1).

11. Define the Recursive/Iterative Step

12. Recursive DFS: 1 + max(maxDepth(root.left), maxDepth(root.right)).
13. Iterative DFS: Stack stores (node, current_depth). Pop, update max depth, push children.

14. BFS: Queue stores (node, current_depth). Dequeue, update max depth, enqueue children.

15. Handle Edge Cases

16. Empty tree (root = None).
17. Single-node tree (root.left = root.right = None).

18. Skewed tree (e.g., all left children).

19. Test with Examples

20. Draw a small tree (3-5 nodes) and walk through the code manually.

21. Verify edge cases (empty, single node, skewed).

22. Optimize (If Needed)

23. Recursion → Iterative if stack overflow is a risk.

24. BFS → Use a queue (FIFO) for level-order traversal.

25. Analyze Complexity

26. Time: O(n) (visit every node once).
27. Space:
    • Recursive: O(h) (call stack, where h = tree height).
    • Iterative DFS: O(h) (stack).
    • BFS: O(n) (queue in worst-case balanced tree).

? WORKED EXAMPLES

Example 1 – Basic: Maximum Depth of a Binary Tree

Problem: Given the root of a binary tree, return its maximum depth. Example:

    3

   / \
  9  20

    /  \

   15   7

Output: 3 (path 3 → 20 → 15 or 3 → 20 → 7).

Solution (Recursive DFS)

def maxDepth(root):

    if not root:

        return 0

    return 1 + max(maxDepth(root.left), maxDepth(root.right))

Why this works: - Base case: Empty tree has depth 0. - Recursive case: The depth of the current node is 1 (for itself) plus the maximum depth of its left/right subtrees. - Divide & Conquer: Solves left/right subtrees independently and combines results.

Complexity: - Time: O(n) (visit every node once). - Space: O(h) (call stack, where h = tree height; worst-case O(n) for skewed trees).

Example 2 – Medium: Maximum Depth of an N-ary Tree

Problem: Given an N-ary tree, return its maximum depth. Example:

       1

    /  |  \

   3   2   4
  / \
 5   6

Output: 3 (path 1 → 3 → 5 or 1 → 3 → 6).

Solution (Recursive DFS)

class Node:

    def __init__(self, val=None, children=None):

        self.val = val

        self.children = children if children else []

def maxDepth(root):

    if not root:

        return 0

    max_child_depth = 0

    for child in root.children:

        max_child_depth = max(max_child_depth, maxDepth(child))

    return 1 + max_child_depth

Why this works: - Base case: Empty tree has depth 0. - Recursive case: For each child, compute its depth and take the maximum. - Generalization: Works for any number of children (not just binary trees).

Complexity: - Time: O(n) (visit every node once). - Space: O(h) (call stack).

Example 3 – Hard/Follow-up: Diameter of a Binary Tree

Problem: Given the root of a binary tree, return the length of the diameter (longest path between any two nodes, which may or may not pass through the root). Example:

      1

     / \

    2   3

   / \
  4   5

Output: 3 (path 4 → 2 → 5 or 5 → 2 → 1 → 3).

Solution (Recursive DFS with State Tracking)

def diameterOfBinaryTree(root):

    diameter = 0


    def depth(node):

        nonlocal diameter

        if not node:

            return 0

        left_depth = depth(node.left)

        right_depth = depth(node.right)

        diameter = max(diameter, left_depth + right_depth)

        return 1 + max(left_depth, right_depth)


    depth(root)

    return diameter

Why this works: - Key Insight: The diameter at a node is left_depth + right_depth. - State Tracking: Use a nonlocal variable to track the maximum diameter seen so far. - Recursive DFS: Compute depth of left/right subtrees while updating the diameter.

Complexity: - Time: O(n) (visit every node once). - Space: O(h) (call stack).

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap

"Alright, let’s lock this in. For maximum depth problems, start with recursive DFS—it’s the simplest and most intuitive. Base case: empty tree returns 0. Recursive case: 1 plus the max depth of left and right subtrees. If recursion depth is a concern, switch to iterative DFS with a stack or BFS with a queue. For follow-ups like diameter, track state during recursion. Always test edge cases: empty tree, single node, skewed trees. Time complexity is O(n), space is O(h) for recursion or O(n) for BFS. You’ve got this—now go crush that interview!

? Final Notes

• Practice: Solve variations (e.g., minimum depth, balanced tree check).
• Whiteboard: Draw the tree and walk through the code step-by-step.
• Confidence: This problem is a confidence-builder—master it, and you’ll handle harder tree problems with ease.