The blog for Design Patterns, Linux, HA and Myself!

Range Sum of BST - Leetcode

Leetcode Solution: Understand Leetcode problem Range Sum of BST(938) With a Brute Force and Optimal Solution

In this article we’ll be solving the problem: Range Sum of BST. We’ll proceed with a brute force approach, and then we’ll be using a more optimal approach to solve the problem.

Given the root node of a binary search tree, return the sum of values of all nodes with value 
between L and R (inclusive). The binary search tree is guaranteed to have unique values.

Example 1:
    Input: root = [10,5,15,3,7,null,18], L = 7, R = 15
    Output: 32

Example 2:
    Input: root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
    Output: 23
    The number of nodes in the tree is at most 10000.
    The final answer is guaranteed to be less than 2^31.


We’ll be using the following tree as the input to solve the problem:


If the value of the L and R is 7 and 15 then we’ll be selecting these nodes:

Solution 1
The sum will be 10 + 7 + 15 = 32

and, if the values for L and R are 4 and 15 then the selected nodes will be:

Solution 2
The sum will be 4 + 5 + 7 + 10 + 15 = 41

Keep in mind that the input tree will always be a binary search tree(BST) which means that values of the left children will always be lower than the current node, and the values of the right children will always be greater than the current node.

The very first approach that can be applied here could be a simple tree traversal. We will traverse through all the nodes , if the value is between L and R(inclusive) then we’ll add it to the ongoing sum other we’ll ignore it. This code block should provide the correct output for our brute force approach:

sum := 0
func preOrder(root TreeNode, L, R int) {
    if root == nil {
    if root.Val >= L && root.Val <= R {
        sum += root.Val
    preOrder(root.Left, L, R)
    preOrder(root.Right, L, R)

One information that we’ve not utilized in our solution is that the input tree will always be a BST. The current solution can be optimized if we utilize this information.

Let do a dry run of our approach here. L = 7 and R = 15.

  1. We start at 10. The value is between L and R, We add it to the sum. We’ll move to 5 next because the current node’s value is between L and R.

    Loop 1

  2. We are at 5 now. We’ll not add value to sum, and we’ll not go to 3 as well because the current node’s values is not between L and R. By ignoring 3, we’ve ignored 1 and 4 as well.

    Loop 2

  3. We’ve moved to 7 and add its value to sum.

    Loop 3

  4. We move to 15 and add it’s value to sum. We’ll not move to 18 now.

    Loop 4

  5. This way we’ve ignored all those nodes whose values are not between L and R.

Here’s the code for this problem. It can be found here on GitHub as well.

type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode

func rangeSumBST(root *TreeNode, L int, R int) int {
	sum := 0
	inOrder(root, L, R, &sum)
	return sum

func inOrder(node *TreeNode, L int, R int, sum *int) {
	sendLeft := false
	sendRight := false
	if node.Val >= L && node.Val <= R {
		*sum = *sum + node.Val
	if node.Left != nil && node.Val > L {
		sendLeft = true
	if node.Right != nil && node.Val < R {
		sendRight = true

	if sendLeft {
		inOrder(node.Left, L, R, sum)
	if sendRight {
		inOrder(node.Right, L, R, sum)


Here the function rangeSumBST calls inOrder to traverse the tree. The inOrder function is modified to handle the optimization that we’ve discussed earlier. Here, we got the left node only if the current node’s value is greater than L. We do the same for the right node as well.

Loading Comments... Disqus Loader
comments powered by Disqus