In a Meta interview setting, you are given the root of a binary tree and two integers low and high. Return the sum of all node values v such that low <= v <= high.
Assume the tree is a binary search tree (BST), which allows you to skip subtrees that cannot contain valid values.
root as a binary tree node (or null), and integers low, high[low, high]Example 1
Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32
Explanation: The values in range are 7, 10, and 15, so the sum is 32.
Example 2
Input: root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
Output: 23
Explanation: The values in range are 6, 7, and 10, so the sum is 23.
[0, 2 * 10^4]1 <= Node.val <= 10^51 <= low <= high <= 10^5A correct solution should use the BST property to avoid unnecessary traversal when possible.
root = [10,5,15,3,7,null,18], low = 7, high = 15Output32WhyThe node values within the inclusive range are 7, 10, and 15.root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10Output23WhyThe valid node values are 6, 7, and 10, so the sum is 23.The number of nodes is in the range [0, 2 * 10^4]1 <= Node.val <= 10^51 <= low <= high <= 10^5The input tree is a valid binary search treedef range_sum_bst(root, low, high):