Description
Return the number of nodes on the longest root-to-leaf path; an empty tree has depth zero.
Solution
import sys
sys.setrecursionlimit(100_000)
def max_depth(root):
if not root:
return 0
return 1 + max(max_depth(root.left), max_depth(root.right))Examples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[1,2,3,null,4]]- Output
3
The path 1, 2, 4 contains three nodes.
Example 2
- Input
[[]]- Output
0
Empty trees have depth zero.
Example 3
- Input
[[8]]- Output
1
A root alone has depth one.
Approach
A node's depth is one plus the greater depth of its children.
Time & space
O(n) time; O(h) recursion space. Here n is the node count, and h is the tree height.