Is Range Sum of BST easy or hard?

Range Sum of BST is classified as an Easy problem on LeetCode with a high acceptance rate. It mainly tests basic tree traversal and understanding of BST properties rather than advanced algorithms.

Range Sum of BST Python/Java solution

A typical Python or Java solution uses recursive DFS. Visit the node, check if its value lies within [low, high], add it to the sum, and recursively explore only the subtrees that could contain valid values. Both languages implement this in O(n) time with O(h) space.

How to solve Range Sum of BST in O(n)?

Traverse the tree using depth-first search and accumulate values that fall inside the range [low, high]. Use the BST property to skip unnecessary branches: ignore the left subtree when node.val high. This guarantees each relevant node is processed once, giving O(n) time.

What is the best approach for Range Sum of BST?

The most common approach is a depth-first search using recursive in-order traversal. Because the structure is a Binary Search Tree, you can prune branches where values are outside the range [low, high]. This keeps the solution simple while maintaining O(n) worst-case time and O(h) space for the recursion stack.

Is Range Sum of BST asked at Google/Amazon/Meta?

Range Sum of BST is a common easy-level tree question that appears in interview preparation lists for companies like Amazon, Google, and Meta. It tests understanding of binary search trees, DFS traversal, and pruning techniques rather than complex algorithms.

What data structure is used in Range Sum of BST?

The problem is based on a Binary Search Tree (BST). Solutions typically use depth-first search traversal with either recursion or an explicit stack to process nodes in-order while leveraging BST ordering to prune branches.

What is the time complexity of Range Sum of BST?

The worst-case time complexity is O(n), where n is the number of nodes in the tree, because each node may be visited once. With BST pruning, many nodes can be skipped in practice. Space complexity is O(h), where h is the height of the tree due to recursion or the traversal stack.

Description Solution Video 6:20

938. Range Sum of BST

Easy87.7% acceptance6 companies

Given the root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].

Example 1:

Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32
Explanation: Nodes 7, 10, and 15 are in the range [7, 15]. 7 + 10 + 15 = 32.

Example 2:

Input: root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
Output: 23
Explanation: Nodes 6, 7, and 10 are in the range [6, 10]. 6 + 7 + 10 = 23.

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.val are unique.

Asked at 6 companies

Meta Yandex

Google Amazon Microsoft Bloomberg

Topics

6:20

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1# Definition for a binary tree node.
2# class TreeNode:
3#     def __init__(self, val=0, left=None, right=None):
4#         self.val = val
5#         self.left = left
6#         self.right = right
7class Solution:
8    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
9        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

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

Input

[10,5,15,3,7,13,18,1,null,6]
6
10

Your code is saved on this device.Solution