Skills101
← All coding problems

Range Sum of BST

easyTrees & BST II+10 XPTime limit 2s

A shop keeps its product prices in a binary search tree (all values distinct; smaller values in the left subtree, larger in the right). A customer asks: what is the total of all prices between lo and hi (both included)?

Tree format. A binary tree is given on one line in level order (top to bottom, left to right), with null for a missing child — the same way most interview platforms show trees. Trailing nulls are left out, and an empty tree is the single word null. Example: 3 9 20 null null 15 7 is

    3
   / \
  9   20
     /  \
    15   7

Input: one BST, then a line lo hi.

Output: the sum of all values v with lo ≤ v ≤ hi (0 if there are none).

Constraints: 0 ≤ nodes ≤ 10⁴, distinct values between −10⁴ and 10⁴, −10⁴ ≤ lo ≤ hi ≤ 10⁴. The tree has at most 10⁴ nodes and its height is at most 500, so recursion is safe in every language.

Think about it: visiting every node works, but the BST order lets you skip whole subtrees: if a node's value is below lo, nothing in its left subtree can be in range; if it is above hi, skip its right subtree.

Sample input 1

10 5 15 3 7 null 18
7 15

Sample output 1

32

Sample input 2

10 5 15 3 7 13 18 1 null 6
6 10

Sample output 2

23

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.