Max Depth Binary Tree LeetCode 104 Guide

LeetCode 104 — Maximum Depth of Binary Tree — gives you the root of a binary tree and asks you to return its maximum depth. Depth is defined as the number of nodes along the longest path from the root node down to the farthest leaf node. A single-node tree has depth 1, and an empty tree has depth 0.

This problem is labeled Easy and is widely considered the canonical introduction to tree recursion. It has a clean two-line recursive solution that embodies the post-order traversal pattern, and it can also be solved iteratively using either a depth-tracking stack or a BFS queue that counts levels. Mastering all three approaches gives you a strong foundation for harder tree problems.

The constraints are minimal: the tree can have between 0 and 10,000 nodes, and node values are integers between -100 and 100. An empty tree (null root) should return 0, which is the natural recursive base case.

The recursive DFS solution is the most elegant approach to this problem. The logic fits in two lines: if the root is null, return 0; otherwise return 1 plus the maximum of the left and right subtree depths. This is a post-order traversal — the function processes both children before combining their results at the current node.

In Python: def maxDepth(root): return 0 if not root else 1 + max(maxDepth(root.left), maxDepth(root.right)). In Java: public int maxDepth(TreeNode root) { return root == null ? 0 : 1 + Math.max(maxDepth(root.left), maxDepth(root.right)); }. Both versions express the same logic with zero auxiliary data structures.

The time complexity is O(n) because every node is visited exactly once. The space complexity is O(h) for the recursion call stack, where h is the height of the tree. For a balanced tree h = O(log n), but for a completely skewed tree h = O(n). The simplicity of this solution makes it the go-to answer in interviews.

The recursive approach works because of the self-similar structure of binary trees. Every node is the root of its own subtree, and the maximum depth of a tree rooted at any node is simply 1 (for that node itself) plus the maximum depth of the deeper of its two subtrees. This relationship holds all the way down to the leaves.

Each recursive call computes the depth of its subtree independently. The parent combines the left and right depths by taking the maximum and adding 1. This bottoms-up aggregation — where results flow from leaves to root — is precisely the post-order traversal pattern. The key insight is that no node needs information from its ancestors to compute its own subtree depth.

This pattern generalizes broadly: balanced binary tree, diameter of binary tree, and path sum problems all rely on the same post-order aggregation where child results bubble up to be combined at the parent. Understanding why max depth works this way is the key to unlocking those harder problems.

The iterative DFS approach uses an explicit stack to simulate the recursion. Instead of pushing just nodes, push (node, depth) pairs — the node to process and the depth at which it sits. Initialize the stack with [(root, 1)] and track a maxDepth variable. Each iteration pops a pair, updates maxDepth if the current depth is larger, then pushes both non-null children with depth+1.

In Python: stack = [(root, 1)] if root else []; maxDepth = 0; while stack: node, depth = stack.pop(); maxDepth = max(maxDepth, depth); if node.left: stack.append((node.left, depth + 1)); if node.right: stack.append((node.right, depth + 1)); return maxDepth. The time complexity is O(n) and the space complexity is O(h) for the stack, mirroring the recursive solution exactly.

This approach is particularly useful when the tree is very deep and recursion depth might overflow the call stack. In Python, the default recursion limit is 1000 frames, which can be hit by a skewed tree with 1001+ nodes. The iterative stack version bypasses this limit entirely, making it safer for production use with large inputs.

The BFS approach uses a queue and processes the tree level by level. Initialize the queue with the root and a depth counter at 0. Each iteration of the outer while loop processes all nodes at the current level: for each node in the queue, dequeue it and enqueue its non-null children. After processing each complete level, increment the depth counter. When the queue is empty, the counter equals the maximum depth.

In Python: from collections import deque; if not root: return 0; q = deque([root]); depth = 0; while q: depth += 1; for _ in range(len(q)): node = q.popleft(); if node.left: q.append(node.left); if node.right: q.append(node.right); return depth. The len(q) snapshot at the start of each level is the key — it tells you exactly how many nodes belong to the current level.

The time complexity is O(n) since every node is processed once. The space complexity is O(w) where w is the maximum width of the tree — the largest number of nodes at any single level. For a complete binary tree the last level can contain n/2 nodes, giving O(n) space. BFS is the most natural solution when you need level-by-level information.

Python recursive (2 lines): def maxDepth(root): return 0 if not root else 1 + max(maxDepth(root.left), maxDepth(root.right)). Python iterative DFS (~8 lines): stack = [(root, 1)] if root else []; res = 0; while stack: node, d = stack.pop(); res = max(res, d); if node.left: stack.append((node.left, d+1)); if node.right: stack.append((node.right, d+1)); return res. Python BFS (~8 lines): uses deque with level-by-level processing as shown above.

Java recursive: public int maxDepth(TreeNode root) { return root == null ? 0 : 1 + Math.max(maxDepth(root.left), maxDepth(root.right)); }. Java BFS: Queue<TreeNode> q = new LinkedList<>(); if (root != null) q.add(root); int depth = 0; while (!q.isEmpty()) { int size = q.size(); depth++; for (int i = 0; i < size; i++) { TreeNode n = q.poll(); if (n.left != null) q.add(n.left); if (n.right != null) q.add(n.right); } } return depth;.

All three versions run in O(n) time. Space complexity is O(h) for recursive and iterative DFS, O(w) for BFS where w is max width. In practice, for balanced trees these are both O(log n). For interview purposes, the recursive solution is recommended for its brevity. For production with deeply skewed inputs, prefer iterative DFS or BFS to avoid stack overflow.

Minimum Depth of Binary Tree (LeetCode 111) is the natural complement to this problem. Instead of taking the max of left and right subtree depths, you take the minimum — but with a critical twist: you must not count a null subtree as a valid leaf path. A node with only one child has minimum depth passing through that child, not through the null side.

Balanced Binary Tree (LeetCode 110) and Diameter of Binary Tree (LeetCode 543) both build directly on the max depth pattern. Balanced Binary Tree checks whether the height difference between left and right subtrees is at most 1 at every node — requiring the same post-order DFS aggregation. Diameter of Binary Tree finds the longest path through any node, combining left and right depths at each step exactly like max depth does.

Together, Maximum Depth, Minimum Depth, Balanced Binary Tree, and Diameter of Binary Tree form the tree depth family — four problems that all rely on the same post-order aggregation pattern where child results bubble up to be combined at the parent. Mastering this family prepares you for Binary Tree Maximum Path Sum (LeetCode 124), which is the most complex problem in this group.