L14. Maximum Depth in Binary Tree | Height of Binary Tree

Calculating the maximum depth (or height) of a binary tree is a foundational problem in data structures and algorithms. This module explores how to compute this depth efficiently using both recursive and level-order traversal strategies, complete with complexity analyses and production-ready implementations in C++ and Java.

1. Problem Statement & Definition of Maximum Depth

The maximum depth (often referred to as the height) of a binary tree is defined as the number of nodes along the longest path from the root node down to the farthest leaf node.

• A tree with a single root node has a depth of 1.
• An empty tree (where the root is null) has a depth of 0.

        Root (1)
           / \
         (2) (3)
             / \
           (4) (6)
           /
         (5)

In the example tree above, the longest path goes 1 -> 3 -> 4 -> 5, giving a maximum depth/height of 4.

2. Core Mental Model: The Recursive Subproblem

When standing at any arbitrary node in a binary tree, we do not need to manually trace every single path across the entire structure at once. Instead, we can break the problem down into a self-similar subproblem:

Core Insight: The maximum depth starting from any node is equal to 1 (accounting for the current node itself) plus the maximum of the depths of its left subtree and right subtree.

Mathematical Recurrence Relation

• Base Case: If the node is null (it does not exist), its depth is 0.

3. Step-by-Step Tree Dry Run Walkthrough

Let us trace how the recursive approach computes the height for our example tree:

        1
       / \
      2   3
         / \
        4   6
       /
      5

1. Start at Root (1): We need 1 + max(leftHeight, rightHeight). We explore the left child (2) first.
2. At Node 2:
   • Left child is null (height 0).
   • Right child is null (height 0).
   • Height of node 2 = $1 + \max(0, 0) = \mathbf{1}$. Returns 1 to Root 1.
3. Back to Root (1): Left subtree height is 1. Now we explore the right child (3).
4. At Node 3: We need $1 + \max(\text{left}, \text{right})$. We explore node 3's left child (4).
5. At Node 4: We explore its left child (5).
6. At Node 5:
   • Left child is null (0), Right child is null (0).
   • Height of node 5 = $1 + \max(0, 0) = \mathbf{1}$. Returns 1 to Node 4.
7. Back to Node 4: Left child returned 1, right child (null) is 0.
   • Height of node 4 = $1 + \max(1, 0) = \mathbf{2}$. Returns 2 to Node 3.
8. At Node 6 (Right child of 3):
   • Left and right children are null.
   • Height of node 6 = $1 + \max(0, 0) = \mathbf{1}$. Returns 1 to Node 3.
9. Back to Node 3: Left child (4) returned 2, right child (6) returned 1.
   • Height of node 3 = $1 + \max(2, 1) = \mathbf{3}$. Returns 3 to Root 1.
10. Final Calculation at Root (1): Left subtree returned 1, right subtree returned 3.
    • Total Max Depth = $1 + \max(1, 3) = \mathbf{4}$.

4. Naive vs. Optimal Traversal Strategies

When solving tree depth problems, developers generally choose between two primary traversal paradigms:

5. Complete Implementation Code

C++ Implementation

#include <iostream>
#include <algorithm>

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int maxDepth(TreeNode* root) {
        // Base case: if the node is null, depth is 0
        if (root == nullptr) {
            return 0;
        }
        
        // Recursively compute left and right subtree depths
        int leftHeight = maxDepth(root->left);
        int rightHeight = maxDepth(root->right);
        
        // Current depth is 1 (for the root) + max of subtrees
        return 1 + std::max(leftHeight, rightHeight);
    }
};

Java Implementation

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { 
        val = x; 
        left = null;
        right = null;
    }
}

class Solution {
    public int maxDepth(TreeNode root) {
        // Base case: if the node is null, depth is 0
        if (root == null) {
            return 0;
        }
        
        // Recursively compute left and right subtree depths
        int leftHeight = maxDepth(root.left);
        int rightHeight = maxDepth(root.right);
        
        // Current depth is 1 (for the root) + max of subtrees
        return 1 + Math.max(leftHeight, rightHeight);
    }
}

6. Complexity Analysis

• Time Complexity: $\mathcal{O}(N)$, where $N$ is the total number of nodes in the binary tree. Every single node must be visited at least once to account for its contribution to the height. This is asymptotically optimal because you cannot verify the depth without inspecting all nodes.
• Space Complexity:
  • Balanced Tree: $\mathcal{O}(\log N)$ auxiliary stack space due to the recursive call stack height.
  • Skewed Tree (Linear/Degenerate Tree): $\mathcal{O}(N)$ auxiliary stack space in the absolute worst case where every node has only one child (forming a straight line).

7. Summary and Key Takeaways

• Definition: The maximum depth of a binary tree is the length of the longest path from the root node to the deepest leaf node.
• Optimal Recurrence: $1 + \max(\text{leftSubtreeDepth}, \text{rightSubtreeDepth})$ encapsulates the entire logic cleanly.
• Base Case: Always handle the null node condition by returning 0 to terminate recursive calls safely.
• Traversal Options: Both recursive (DFS) and level-order (BFS) approaches can solve this, but recursion is favored when tree heights are balanced ($\mathcal{O}(\log N)$ space).
• Time Complexity Bound: $\mathcal{O}(N)$ time is strictly required since every node must be visited.
• Worst-Case Space: Skewed linear trees consume $\mathcal{O}(N)$ call stack space, whereas balanced trees consume $\mathcal{O}(\log N)$ stack space.