Maximum Depth of Binary Tree: recursive DFS

• Maximum Depth is the number of nodes along the longest root-to-leaf path in a binary tree.
• Recursive formula is 1 + Math.max(depth(left), depth(right)) with depth(null) = 0.
• Post-order style means the parent cannot compute its depth until both children have reported theirs.
• Time is O(n) because every node is visited exactly once.
• Space is O(h) for the call stack, where h is the tree height.

What is Maximum Depth of a Binary Tree?

The maximum depth of a binary tree is the number of nodes along the longest path from the root node down to the farthest leaf node. It is sometimes called the height of the tree. This is one of the most fundamental recursive tree problems because the definition of depth is itself recursive.

package com.bank.service;

public class HierarchyDepthService {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        return 1 + Math.max(leftDepth, rightDepth);
    }
}

Why does this problem matter in banking systems?

In loan approval hierarchies at the National Bank of India, a chain that is too deep means a loan could take too many approval hops and breach the service-level agreement. Rajesh measures the longest escalation chain and raises a warning when it exceeds the allowed threshold. The recursive depth computation gives this answer in a single pass.

How does the recursion work internally?

The base case is a null node, which returns 0. This single line handles both empty trees and the bottom of every branch. For a non-null node, you recursively ask both children for their depths, take the maximum of the two, and add 1 to count the current node. This is a post-order computation because you need both children's answers before computing the parent's.

// Step-by-step trace for this tree:
//        1
//       / \
//      2    3
//     /
//    4
//
// maxDepth(4) = 1 + max(0, 0) = 1
// maxDepth(2) = 1 + max(1, 0) = 2
// maxDepth(3) = 1 + max(0, 0) = 1
// maxDepth(1) = 1 + max(2, 1) = 3

Output: 3

How is recursive DFS different from iterative BFS?

The recursive approach uses the call stack implicitly. The iterative BFS approach uses a queue and counts the number of levels. Both give the same answer, but BFS avoids deep recursion.

| Aspect | Recursive DFS | Iterative BFS |
|--------|--------------|---------------|
| Data structure | Call stack (implicit) | Queue (explicit) |
| Space | O(h) worst case O(n) | O(w) where w is max width |
| Stack overflow risk | Yes, on skewed trees | No |
| Code complexity | 3 lines | 10-15 lines |

// Iterative BFS approach
public int maxDepthBFS(TreeNode root) {
    if (root == null) return 0;
    java.util.Queue<TreeNode> queue = new java.util.LinkedList<>();
    queue.offer(root);
    int depth = 0;
    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        depth++;
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }
    return depth;
}

What are the rules and constraints?

• A null tree has depth 0.
• A tree with only one node (the root) has depth 1.
• The depth always counts nodes, not edges. Some definitions count edges, which gives a result one less. Clarify with the interviewer.
• The maximum depth is always at least 1 for a non-empty tree.

What are edge cases?

• Empty tree (null root): returns 0.
• Single node: returns 1.
• Completely skewed tree (all left or all right children): depth equals the number of nodes.
• Perfect binary tree with n nodes: depth is log2(n + 1).

// Edge case: skewed tree (linked list shape)
//  1
//   \
//    2
//     \
//      3
// maxDepth = 3, recursion depth = 3
// For 1 million nodes, this causes StackOverflowError

What are common mistakes?

The first mistake is returning 1 for a null node instead of 0, which overcounts by 1 at every leaf. The second mistake is forgetting to add 1 for the current node, which undercounts by 1 at every level.

// WRONG: null returns 1 instead of 0
if (root == null) return 1; // overcounts

// WRONG: forgets to count the current node
return Math.max(maxDepth(root.left), maxDepth(root.right)); // undercounts

// CORRECT:
if (root == null) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));

What about thread safety?

The recursive solution is inherently thread-safe because it uses only local variables and the call stack. No shared mutable state is involved. If the tree structure itself is being modified concurrently, you need external synchronization on the tree, not on the depth computation.

What should a senior engineer know?

For very deep trees with millions of nodes in a skewed shape, the recursive approach overflows the Java call stack, which defaults to about 512 KB. The iterative BFS avoids this entirely. You can also increase the stack size with -Xss, but the BFS approach is the production-safe choice.

The same recursive pattern applies to computing minimum depth, diameter, balanced check, and subtree sum. Mastering this three-line recursion is the foundation for all post-order tree computations.