The problem
Given the root of a binary tree, return its maximum depth: the number of nodes on the longest path from the root down to a leaf (a node with no children).
Examples
01
- Input
root = [3, 9, 20, null, null, 15, 7]
- Output
3
02
- Input
root = [1, null, 2]
- Output
2
Constraints
- 0 ≤ number of nodes ≤ 10⁴
- −100 ≤ Node.val ≤ 100
The idea
The depth of a tree is one (for the root) plus the depth of its deeper subtree. The depth of an empty tree is 0.
A depth-first search — going all the way down one branch before trying the next — computes the depths from the leaves back up: every node learns its children’s depths, then reports its own.
- Time
- O(n)
- Space
- O(h) — h the height, n on a tree that is one long line
Solution · every language run against every case
class Solution: def maxDepth(self, root: Optional[TreeNode]) -> int: # An empty tree has depth 0; otherwise one for this node plus the deeper side. if not root: return 0 return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))