Maximum Depth of Binary Tree Solution Explained

Data Structures / Tree

Maximum Depth of Binary Tree

Easy

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

Maximum depth is defined as the number of nodes along the longest path from the root node down to the farthest leaf node.

Example

Input: root = [3,9,20,null,null,15,7]
Output: 3

Tree Structure:

      3
     / \
    9  20
      /  \
     15   7

Explanation: The longest path is 3 → 20 → 7 (or 3 → 20 → 15), which has 3 nodes.

Understanding the Problem

The depth of a binary tree is the length of the longest path from the root to any leaf node. A leaf node is a node with no children.

Key observations:

An empty tree (null root) has depth 0
A tree with only the root node has depth 1
For any node, the depth is 1 + max(left_child_depth, right_child_depth)

This problem is a perfect candidate for recursion because the depth calculation follows a natural recursive pattern.

Recursive Approach

The recursive solution breaks down the problem into smaller subproblems:

Base case: If the node is null, return 0 (empty tree has no depth)
Recursively calculate the depth of the left subtree
Recursively calculate the depth of the right subtree
Return 1 + max(left_depth, right_depth)

The call stack handles all the bookkeeping. Each recursive call adds 1 to the maximum depth of its children, naturally building up the total depth as the recursion unwinds.

Idea Map

Start at Root

If node == null: return 0

Calculate left_depth = recurse on left child

Calculate right_depth = recurse on right child

Return 1 + max(left_depth, right_depth)

Return Depth

Complexity Analysis

Time Complexity

O(n) - We visit each node exactly once, where n is the number of nodes in the tree.

Space Complexity

O(h) - Call stack depth equals tree height h. Worst case O(n) for skewed tree, O(log n) for balanced tree.

Code


def maxDepth(root):
Initializes the function `maxDepth` which takes the `root` of a binary tree as input.
    if not root:
Base case: if the root is None (null), we have an empty tree with depth 0.
        return 0
Return 0 for empty tree (no nodes).
    left_depth = maxDepth(root.left)
Recursively calculate the depth of the left subtree by calling maxDepth on left child.
    right_depth = maxDepth(root.right)
Recursively calculate the depth of the right subtree by calling maxDepth on right child.
    return 1 + max(left_depth, right_depth)
Add 1 for current node, plus the maximum depth between left and right subtrees.


public int maxDepth(TreeNode root) {
Initializes the function `maxDepth` which takes the `root` of a binary tree as input.
    if (root == null) {
Base case: if the root is null, we have an empty tree.
        return 0;
Return 0 for empty tree (no nodes).
    }
End of the if statement.
    int leftDepth = maxDepth(root.left);
Recursively calculate the depth of the left subtree.
    int rightDepth = maxDepth(root.right);
Recursively calculate the depth of the right subtree.
    return 1 + Math.max(leftDepth, rightDepth);
Add 1 for current node, plus the maximum depth between left and right subtrees using Math.max().
}
End of the function.


int maxDepth(TreeNode* root) {
Initializes the function `maxDepth` which takes a pointer to the `root` of a binary tree.
    if (root == nullptr) {
Base case: if the root is nullptr, we have an empty tree.
        return 0;
Return 0 for empty tree (no nodes).
    }
End of the if statement.
    int leftDepth = maxDepth(root->left);
Recursively calculate the depth of the left subtree using arrow operator.
    int rightDepth = maxDepth(root->right);
Recursively calculate the depth of the right subtree using arrow operator.
    return 1 + max(leftDepth, rightDepth);
Add 1 for current node, plus the maximum depth between left and right subtrees using max().
}
End of the function.

Edge Cases & Common Mistakes

⚠️

Forgetting the base case

Always check if the node is null first. Without this base case, you'll get a null pointer exception when trying to access node.left or node.right.

💡

Using min() instead of max()

The problem asks for the maximum depth, so use max() to find the longer path. Using min() would give you the shortest path to a leaf.

✓

Empty tree input

If the root is null (empty tree), the correct answer is 0. Don't assume the tree always has at least one node.

What is Recursion?

Recursion is a programming technique where a function calls itself to solve smaller instances of the same problem. It's particularly useful for tree problems because trees are naturally recursive structures - each subtree is itself a tree.

Learn more about recursion →

lightbulb

Disclaimer: This problem is for educational purposes. Practice the 'Maximum Depth of Binary Tree' problem on LeetCode.

AlgoExplained.dev