Blind 75Easy
Maximum Depth of Binary Tree — DFS Height Calculation
Return 1 plus the maximum depth of left and right subtrees using recursion.
TreeDFS
Problem Statement
Return the maximum depth (number of nodes along longest path) of a binary tree.
Why This Problem Matters
- Introductory recursion question for binary trees.
- Provides building block for diameter, balance, and AVL problems.
- Demonstrates divide-and-conquer on tree structures.
Thought Process
Base case
Null node depth is 0; single node depth is 1.
Recursive step
Depth = 1 + max(depth(left), depth(right)).
Iterative alternative
Level-order traversal counting levels also works.
Step-by-Step Reasoning
- If node null return 0.
- Compute leftDepth and rightDepth recursively.
- Return 1 + Math.max(leftDepth, rightDepth).
Dry Run
Balanced tree depth 3
Recursion returns 3 after exploring all branches.
Skewed tree 4 nodes
Depth equals 4 due to longest path.
Complexity Analysis
Time
O(n)
Space
O(h)
Why
Each node visited once; recursion depth equals tree height.
Annotated Solution
JAVA
public class MaximumDepthOfBinaryTree {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) { this.val = val; }
}
}Depth is one plus the maximum of child depths; recursion naturally expresses the definition.
Common Pitfalls
- Returning Math.max without +1 forgets to count current node.
- Misinterpreting depth vs number of edges leads to off-by-one errors; confirm definition with interviewer.
- Stack overflow on very deep trees; iterative BFS can mitigate.
Follow-Up Questions
- How would you compute minimum depth?
- Can you determine whether the tree is balanced while computing depth?
Key Takeaways
Tree height recursion is a standard template; know it cold.
Clarify whether depth counts nodes or edges.
Level-order BFS offers an iterative alternative if recursion is undesirable.