PreviousNext
Coding/Graphs and trees

Range sum in BST

Write codeEasy15 minMeta style

Your task

Given a binary search tree as a level-order list (None marks a missing child; children of None are omitted) and an inclusive value range [lo, hi], return the sum of values of all nodes with value in [lo, hi]. Exploit the BST property to prune subtrees that cannot contain in-range values. An empty tree sums to 0.

Examples

bst_range_sum(level: list, lo: int, hi: int) -> int
Example 1
Inputbst_range_sum([10, 5, 15, 3, 7, None, 18], 7, 15)
Output32