Week 2: Binary Tree/Recursion Coding Interview Challenge
Maximum depth of a binary tree
Problem
You’re given the root of a binary tree.
Write a recursive function maxDepth(root) that returns the maximum depth (height) of the tree, where an empty tree has depth 0.
You may assume each node has left and right pointers (or null) to its children.
Pseudocode signature:
function maxDepth(node: TreeNode): integerPart 1 — Code
Implement maxDepth recursively.
Do not use any global variables or mutable state outside the function.
Part 2 — Explain time complexity
In 3–5 sentences, explain the time complexity of your recursive solution.
Your explanation should:
State what work happens in a single call (besides the recursive calls).
Argue why every node in the tree is visited exactly once.
Conclude that the running time is O(n), where n is the number of nodes.
Part 3 — Explain recursion stack depth
In another 3–5 sentences, explain the space complexity in terms of the recursion stack.
Your explanation should:
Describe what one stack frame represents in this function (a call waiting for its children’s depths).
Relate the maximum number of simultaneous frames to the height h of the tree, and state that the extra space is O(h).
Connect that to shapes of the tree:
Balanced tree: h ≈ log n
Worst-case skewed tree: h ≈ n (so stack space can grow to O(n)).
You can invite readers to submit both their code and their written complexity explanations as their “interview answer.”
How to participate
Post your solution as a comment (or link a gist) by noon Pacific Time on March 19, 2026.
Include:
Your language
Brief explanation of your approach
Stated complexity
What I’ll do
On or before March 21, I’ll:.
Publish a Review & Lessons post with:
Detailed feedback on selected solutions
A clean reference solution
Notes on how an interviewer would evaluate your approach.
If you’re short on time this week, at least sketch your approach in prose—that’s still valuable practice.