Maximum Depth of Binary Tree
Mahabharata — The Deepest Root — How Far Does the Tree Extend?
शून्य के लिए — शून्य। अन्यथा — 1 + अधिकतम(बायाँ, दायाँ)। सबसे गहरी शाखा — यही अधिकतम गहराई॥
*For null — zero. Otherwise — 1 + max(left, right). The deepest branch — that is the maximum depth.*
The Story
Find the maximum depth (height) of a binary tree.
For tree `[3,9,20,null,null,15,7]`: max depth=3. For tree `[1,null,2]`: max depth=2.
This is one of the most elegant recursive problems: ```java public int maxDepth(TreeNode root) { if (root == null) return 0; return 1 + Math.max(maxDepth(root.left), maxDepth(root.right)); } ```
One line captures the entire algorithm: the depth of a tree is 1 (for the current node) plus the maximum depth of either subtree.
**BFS level-count alternative:** ```java if (root == null) return 0; Queue<TreeNode> q = new LinkedList<>(); q.offer(root); int depth=0; while (!q.isEmpty()) { depth++; int size=q.size(); for (int i=0;i<size;i++) { TreeNode n=q.poll(); if (n.left!=null) q.offer(n.left); if (n.right!=null) q.offer(n.right); } } return depth; ``` BFS counts levels; the total number of levels = max depth.
Trace `[3,9,20,null,null,15,7]`: - maxDepth(3) = 1 + max(maxDepth(9), maxDepth(20)) - maxDepth(9) = 1 + max(0, 0) = 1 - maxDepth(20) = 1 + max(maxDepth(15), maxDepth(7)) = 1 + max(1,1) = 2 - maxDepth(3) = 1 + max(1, 2) = 3 ✓
The BFS Level Count
Count number of BFS levels. O(n), O(n) for queue.
public int maxDepthBFS(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root); int depth = 0;
while (!q.isEmpty()) {
depth++; int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode n = q.poll();
if (n.left != null) q.offer(n.left);
if (n.right != null) q.offer(n.right);
}
}
return depth;
}The One-Line Recursive Wisdom
public int maxDepth(TreeNode root) {
if (root == null) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}Step-by-Step Walkthrough
Null tree: return 0 ✅ Single node [1]: 1+max(0,0)=1 ✅
Deep Insight
**Foundation problem:** maxDepth is used as a helper in: - tr-20 (Balanced Binary Tree): check |height(left) - height(right)| ≤ 1 - tr-21 (Diameter): diameter = max(height(left) + height(right)) across all nodes - tr-22 (Tilt): similar post-order computation
**Height vs Depth:** In tree terminology: - Depth of a node = distance from root to that node - Height of a node = distance from that node to the deepest leaf below it - maxDepth of tree = height of root = depth of deepest leaf
**One-liner elegance:** This is a textbook example of recursion's power: the entire algorithm fits in a single return statement, expressing the recursive structure clearly.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(n) | BFS queue |
| Optimal | O(n) | O(h) | Recursive; O(h) call stack |
Pattern Recognition
✅ Max depth: 1 + max(left, right) ✅ Base: null → 0 ✅ Foundation for height-based tree problems ✅ BFS alternative: count levels **LeetCode Trigger Phrases:** → "maximum depth of binary tree" → Height of binary tree → Foundation for balanced/diameter problems
Bhagavad Gita 15.1
ऊर्ध्वमूलमधःशाखमश्वत्थं प्राहुरव्ययम्। छन्दांसि यस्य पर्णानि यस्तं वेद स वेदवित्॥
They speak of an imperishable Ashvattha tree with roots above and branches below. Its leaves are the Vedic hymns; one who knows this tree knows the Vedas.
Connection: The maximum depth measures how deeply the tree's branches extend downward from its root. The Ashvattha tree, with roots above and branches below, represents the cosmic tree of existence — its maximum depth is the farthest extent of manifestation from the divine root. maxDepth(tree) = 1 + max of its two greatest branches, just as the universe's depth is the extent of creation from its divine source.