Band Sum in a Search Tree

Easy

You get the root of a binary search tree: for every node, all values in its left subtree are smaller than its own value and all values in its right subtree are larger. All values are distinct. You also get two bounds, lo and hi. Return the sum of the values of all nodes that fall within the band from lo to hi, inclusive. Think about how the ordering of the tree lets you skip branches that cannot contain any answer.

Example 1

root=tree_node([8, 3, 12, 1, 5, 10, 15]), lo=4, hi=11 → 23

The band [4, 11] contains 5, 8 and 10: 5 + 8 + 10 = 23.

Example 2

root=tree_node([20, None, 30]), lo=1, hi=10 → 0

Every value is above 10, so the sum is empty: 0.

Constraints

The tree has between 1 and 2 · 10⁴ nodes
1 ≤ Node.val ≤ 10⁵
1 ≤ lo ≤ hi ≤ 10⁵
All values are distinct and the tree is a valid search tree

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Binary Search Tree Binary Tree

Similar problems

Nearest Value in a Search Tree Easy Most Frequent Values in a Search Tree Easy Pair Sum in a Search Tree Easy Closest Pair in a Search Tree Easy Search Tree Into a Line Easy

Input

root=tree_node([8, 3, 12, 1, 5, 10, 15]), lo=4, hi=11

Expected

Run checks the first 3 tests in your browser. Submit checks all 53 tests on the server, hidden ones included.