Week 2: Reviews and Feedback
Recursive Tree Depth: Comparing a Clean Java Solution to an Over‑Engineered Python One
1. Restating the challenge
Given the root of a binary tree, return its maximum depth (height): the number of nodes along the longest path from the root down to the farthest leaf. An empty tree has depth 0.
2. A clean Java solution
This is an “interview‑ready” version: short, idiomatic, and closely aligned with the recursive definition of tree height.
// Definition for a binary tree node.
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution {
// Returns the maximum depth (height) of the binary tree.
public int maxDepth(TreeNode root) {
// Base case: empty subtree has depth 0
if (root == null) {
return 0;
}
// Recursively compute depth of left and right subtrees
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
// Current node’s depth = 1 (this node) + deeper of the two subtrees
return 1 + Math.max(leftDepth, rightDepth);
}
}How to explain it in an interview
Think in terms of subtrees: the depth of the whole tree is 1 plus the maximum of the depths of the left and right subtrees.
The recursion mirrors that definition: if the subtree is empty, the depth is 0; otherwise, recur on children and take
1 + max(left, right).
3. A “not‑so‑good but correct” Python solution
Here’s a version that technically works, but takes the scenic route and makes the recursion harder than it needs to be. It’s the kind of thing an unsure candidate might write under pressure.
from typing import Optional, List, Tuple
class TreeNode:
def __init__(self, val: int = 0,
left: 'Optional[TreeNode]' = None,
right: 'Optional[TreeNode]' = None):
self.val = val
self.left = left
self.right = right
def max_depth_bad(root: Optional[TreeNode]) -> int:
# Handle the trivial case explicitly
if root is None:
return 0
# We'll store (node, depth) pairs for *every* node
all_nodes: List[Tuple[TreeNode, int]] = []
def dfs(node: Optional[TreeNode], depth: int) -> None:
# Redundant base case checks & side effects
if node is None:
return
# Record this node and its depth in a list
all_nodes.append((node, depth))
# Recurse on children, but keep incrementing depth manually
if node.left is not None:
dfs(node.left, depth + 1)
else:
# unnecessary branch
dfs(None, depth + 1)
if node.right is not None:
dfs(node.right, depth + 1)
else:
# unnecessary branch
dfs(None, depth + 1)
# Start DFS from root at depth 1
dfs(root, 1)
# Now compute maximum depth by scanning the list we built
max_d = 0
for (_, d) in all_nodes:
if d > max_d:
max_d = d
return max_dWhat’s “bad” about it?
It keeps an extra list of all nodes and depths, then scans that list to find the max, rather than just returning the depth directly from recursion. This adds both time and space overhead.
It makes unnecessary recursive calls on
None, deepening the call stack without any benefit and increasing the chance of hitting recursion‑limit issues on tall trees.The control flow is more complicated than the simple “1 + max(left, right)” pattern, which makes it harder to see the recursion invariant.
4. Time complexity: same big‑O, very different clarity
Both implementations ultimately visit each real node exactly once.
In the Java version, it’s easy to see: each node does constant work and makes at most two recursive calls, one to each child.neetcode+1
In the Python version, we still traverse each node once, but we also keep an O(n) list of
(node, depth)pairs and do an extra linear scan at the end. The asymptotic time complexity is still O(n), but with a larger constant factor and more mental overhead.
This is an important interview point: two solutions can share the same big‑O yet differ a lot in simplicity, constants, and how easy they are to verify.
5. Stack depth and space: what the call stack is doing
The clean Java version is also much nicer to reason about in terms of stack depth and auxiliary space.
Every active recursive call corresponds to one node on a single root‑to‑current‑node path, so at any moment the number of frames on the stack is at most the tree height.
That gives auxiliary space O(h):
For a balanced tree, h ≈ log n.
For a skewed “linked‑list‑shaped” tree, h ≈ n, so stack space can grow to O(n).
The Python version shares the same recursion behavior, but then adds an all_nodes list of size O(n) on top of the O(h) call stack. That means its total extra space is O(n) even on a balanced tree, purely due to the way it’s structured.guides.
6. Takeaways
Start from the mathematical definition: “depth of a tree = 0 if empty, else 1 + max(depth of children)”. Code that literally.
Avoid carrying extra global lists or making redundant recursive calls; they rarely help and often make reasoning about complexity harder.
When you explain time and space, tie them directly to “one visit per node” and “one stack frame per level down the tree”.
Here’s an iterative Java section you can drop into the solutions post, contrasting recursion with an explicit data structure.
7. Iterative Java solution: same idea, explicit stack/queue
A great follow‑up is: “What if the tree is so deep that recursion risks stack overflow?” One answer is to do the same depth‑first search iteratively using your own stack.
Iterative DFS with an explicit stack
import java.util.Stack;
import javafx.util.Pair; // or your own simple Pair class
class SolutionIterativeDFS {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
// Stack holds (node, depth) pairs
Stack<Pair<TreeNode, Integer>> stack = new Stack<>();
stack.push(new Pair<>(root, 1));
int maxDepth = 0;
while (!stack.isEmpty()) {
Pair<TreeNode, Integer> current = stack.pop();
TreeNode node = current.getKey();
int depth = current.getValue();
// Update answer
if (depth > maxDepth) {
maxDepth = depth;
}
// Push children with depth + 1
if (node.left != null) {
stack.push(new Pair<>(node.left, depth + 1));
}
if (node.right != null) {
stack.push(new Pair<>(node.right, depth + 1));
}
}
return maxDepth;
}
}This mirrors the recursive logic: the stack now plays the role of the call stack, and each entry tracks “which node” and “what depth we’re at.”
How to talk about complexity
Time: Iterative DFS still visits every node exactly once and does constant work per node, so it runs in O(n) time.
Space: Iterative DFS uses a stack whose maximum size is proportional to the height h of the tree, so O(h) extra space, just like the recursive version.
In the recursive version, the call stack is hidden inside the runtime.
In the iterative version, we build that stack explicitly, but the time and space story is the same: O(n) time, and O(h) for DFS.