Tree Level Sum

Binary TreeBreadth-First SearchTree

Given a binary tree and an integer k, find the sum of the values of all nodes at depth k. The root node is at depth 0.

Example 1

Input

[
  [
    3,
    9,
    20,
    null,
    null,
    15,
    7
  ],
  2
]

Output

Explanation. The binary tree looks like this:\n 3\n / \ \n 9 20\n / \ \n 15 7\nThe nodes at depth 2 are 15 and 7, and their sum is 15 + 7 = 22.

Example 2

Input

[
  [
    1
  ],
  0
]

Output

Explanation. The binary tree consists of a single node, which is at depth 0. Thus, the sum is 1.

Example 3

Input

Output

Explanation. The binary tree looks like this:\n 1\n / \ \n 2 3\n /| |\ \n 4 5 6 7\nThe nodes at depth 3 are 4, 5, 6, and 7, and their sum is 4 + 5 + 6 + 7 = 22.

Follow-up: Can you solve this problem without using additional space proportional to the number of tree nodes?

Constraints:

The binary tree will have at least one node.\nThe value of `k` will be a non-negative integer not greater than the height of the tree.

Views: 3