An office directory is stored as a binary search tree; depth 0 is the root, depth 1 its children, and so on. Given the root and a depth d, return the sum of all values located exactly at depth d. Return 0 if the tree has no nodes at that depth.
Examples
12
/ \
7 18
/ \ / \
3 9 15 22
\
5
Input: root = build_tree([12, 7, 18, 3, 9, 15, 22, None, 5]), d = 2
Output: 49 (3 + 9 + 15 + 22)
Input: root = build_tree([12, 7, 18, 3, 9, 15, 22, None, 5]), d = 3
Output: 5
Constraints
0 <= number of nodes <= 3000,0 <= d <= 5000- Values are distinct integers
Goals
- Process a tree level by level
- Stop once the requested depth has been summed