Trees · Coding problem
Range Sum of a BST
A free coding problem from the BST Floor and Ceil skill. Read it here, then solve it in the app in Java or Python.
- Easy
- Coding problem
- Free
- Java and Python
The problem
Given the root of a binary search tree and two integers lo and hi, return the sum of every node value v with lo <= v <= hi.
Input format
<tree in heap-array format>
lo hi
Example
Input:
7
20 10 30 5 15 null 40
12 30
Output: 65
15 + 20 + 30 = 65. Use the BST order to skip subtrees that can't contain any value in range, instead of visiting every node.
Constraints
1 <= number of nodes <= 50000 <= node value <= 2^31 - 1, all distinct0 <= lo <= hi <= 2^31 - 1
How it's graded
- Run checks your code against the examples. Submit also runs a hidden suite in four groups - basic cases, edge cases, random inputs and performance tests at the size limit - and shows which groups pass, never the hidden inputs.
- Stuck? Hints come in four steps, from a nudge to a code skeleton, each costing part of the points.
- Once you pass, you see the approaches from brute force to optimal, and where your solution lands among them.
More problems in BST Floor and Ceil
Solve it Range Sum of a BST free
No card needed. Lessons, practice questions and easy problems are free forever.
Free plan, no card · 7-day Pro trial · Cancel anytime