Maximum Depth of Binary Tree
Easy· DFS· BFS
Problem
Return the depth of a binary tree, meaning the number of nodes along the longest path from the root down to any leaf. An empty tree has depth 0.
Examples
Input: root = [3,9,20,null,null,15,7]
Output: 3
The path 3 -> 20 -> 15 (or 3 -> 20 -> 7) contains three nodes.
Input: root = [1,null,2]
Output: 2
Constraints
- • 0 <= number of nodes <= 10^4
- • -100 <= Node.val <= 100
Hints & approach
Hint 1
Express the depth of a tree in terms of the depths of its two subtrees.
Hint 2
The depth of a node is 1 plus the larger of its children's depths; null has depth 0.
Approachtry the hints first
Recurse: depth(null) = 0, otherwise depth(node) = 1 + max(depth(left), depth(right)). This visits every node once. An equivalent iterative version runs a BFS and counts how many levels it processes.
Time O(n) · Space O(h)