Binary Tree Bounded Sum

EASY10 pts

You are given the root of a Binary Search Tree (BST) along with two integer boundaries, low and high.

Your task is to compute and return the total sum of all node values that fall within the inclusive range [low, high].

A Binary Search Tree is a tree data structure where for every node:

All values in its left subtree are strictly less than the node's value
All values in its right subtree are strictly greater than the node's value

Utilize the BST property to efficiently traverse only the relevant portions of the tree, avoiding unnecessary exploration of subtrees that cannot contain values within the specified range.

Example

Input

root = [10,5,15,3,7,null,18]
low = 7
high = 15

Output

32

Explanation

The nodes with values 7, 10, and 15 all fall within the range [7, 15]. Summing these values: 7 + 10 + 15 = 32.

Example

Input

root = [10,5,15,3,7,13,18,1,null,6]
low = 6
high = 10

Output

23

Explanation

The nodes with values 6, 7, and 10 fall within the range [6, 10]. Summing these values: 6 + 7 + 10 = 23.

Example

Input

root = [5]
low = 1
high = 10

Output

5

Explanation

The tree contains only a single node with value 5. Since 5 is within the range [1, 10], the sum is simply 5.

Accepted0/0·0% Acceptance

Constraints

The number of nodes in the tree is in the range [1, 2 × 10⁴].
1 ≤ Node.val ≤ 10⁵
1 ≤ low ≤ high ≤ 10⁵
All node values in the tree are unique.

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

low =

high =

root =

[10,5,15,3,7,null,18]

You are given the root of a Binary Search Tree (BST) along with two integer boundaries, low and high.

Your task is to compute and return the total sum of all node values that fall within the inclusive range [low, high].

A Binary Search Tree is a tree data structure where for every node:

All values in its left subtree are strictly less than the node's value
All values in its right subtree are strictly greater than the node's value

Utilize the BST property to efficiently traverse only the relevant portions of the tree, avoiding unnecessary exploration of subtrees that cannot contain values within the specified range.

Binary Tree Bounded Sum

Hints

Binary Tree Bounded Sum

Hints