Maximum Depth of Binary Tree

Find the maximum depth (height) of a binary tree.

10 min read

Time: O(n)

Space: O(1)

Solve on LeetCode

Examples

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

Output:3

Explain:

The tree has nodes 3 -> (9, 20). 20 -> (15, 7). The longest path is 3->20->15 (length 3).

Input:root = [1,null,2]

Output:2

Problem Understanding

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.

Algorithm Strategy (Bottom-Up)

We use Post-order DFS (Bottom-Up) to solve this.

Base Case: If the node is null, its depth is 0.
Recursive Step:
- Ask the Left Child: "What is your max depth?"
- Ask the Right Child: "What is your max depth?"
Calculation: My Depth = max(left_depth, right_depth) + 1.

Interactive Visualization

Step 1 / 15

At Node 3. Asking children for their max depth.

Custom Input

Visualize how the depth values bubble up from the leaves to the root.

Dry Run

Node	Left Depth	Right Depth	Calculation	Return Value
9	0	0	max(0,0) + 1	1
15	0	0	max(0,0) + 1	1
7	0	0	max(0,0) + 1	1
20	1 (from 15)	1 (from 7)	max(1,1) + 1	2
3	1 (from 9)	2 (from 20)	max(1,2) + 1	3

Edge Cases

Empty Tree (Root is null): Return 0.
Single Node: Return 1.
Skewed Tree: Effectively a linked list, depth = N.

Solution

Recursive Bottom-Up approach.

1class Solution:
2    def maxDepth(self, root: Optional[TreeNode]) -> int:
3        if not root:
4            return 0
5        
6        left_depth = self.maxDepth(root.left)
7        right_depth = self.maxDepth(root.right)
8        
9        return max(left_depth, right_depth) + 1

Complexity Analysis

Time: O(N) because we visit every node once.
Space: O(H) for recursion stack. Best case O(log N), worst case O(N).

Previous Problem

Find K Closest Elements

Next Problem

Path Sum