Maximum Depth of Binary Tree
Given the root of a binary tree, return its maximum depth. Solve using recursion (DFS).
Why Interviewers Ask This
Google interviewers use this problem to assess a candidate's fundamental grasp of recursion and tree traversal logic. It evaluates whether you can translate a recursive definition into clean, efficient code without getting lost in edge cases like null nodes or single-node trees. They specifically look for your ability to handle base cases correctly and manage the call stack depth intuitively.
How to Answer This Question
1. Clarify the input: Confirm if the tree is empty (root is null) and define what 'depth' means (number of nodes on the longest path from root to leaf). 2. Define the base case immediately: State that if the node is null, the depth is zero. This prevents infinite recursion. 3. Formulate the recursive step: Explain that the depth of a node is one plus the maximum of its left and right subtree depths. 4. Draft the solution mentally: Visualize the tree structure and how the function unwinds, returning values up the chain. 5. Optimize and discuss complexity: Mention that while this is O(N) time and O(H) space, it is the most readable approach for this specific constraint. 6. Walk through an example: Trace a small tree with three levels to demonstrate the logic flow before writing code.
Key Points to Cover
- Correctly identifying the base case where a null node returns 0
- Using the mathematical formula: 1 + max(left_depth, right_depth)
- Explaining the difference between time complexity O(N) and space complexity O(H)
- Demonstrating clear thought process before writing syntax
- Handling the empty tree edge case explicitly
Sample Answer
To solve this efficiently, I will use a Depth-First Search approach via recursion, which aligns perfectly with the hierarchical nature of binary trees. First, I need to establish my base case. If the current node is null…
Common Mistakes to Avoid
- Returning 1 instead of 0 for the null base case, causing incorrect depth calculations
- Attempting to pass a global counter variable instead of using return values for aggregation
- Confusing maximum depth with minimum depth or failing to take the max of left/right branches
- Neglecting to mention space complexity related to the recursion stack depth
Sound confident on this question in 5 minutes
Answer once and get a 30-second AI critique of your structure, content, and delivery. First attempt is free — no signup needed.