Problem: Maximum Depth of Binary Tree

Problem Statement

Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Approach: Recursive DFS

The depth of a tree is 1 + max(depth of left child, depth of right child).

1. Base Case: If the node is null, its depth is 0.
2. Recursive Step:
   • Call the function on the left child.
   • Call the function on the right child.
   • Return the maximum of the two results plus 1.

Java Implementation

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    
    int leftHeight = maxDepth(root.left);
    int rightHeight = maxDepth(root.right);
    
    return 1 + Math.max(leftHeight, rightHeight);
}

Complexity Analysis

• Time Complexity: $O(n)$. We visit each node once.
• Space Complexity: $O(h)$ where $h$ is the height of the tree, for the recursion stack.

Interview Tips

• Mention that this is essentially a Post-order traversal (process children, then process current node).
• Be ready to implement the iterative version using BFS (level-by-level count).