The blog for Design Patterns, Linux, HA and Myself!
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
Note:
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:
The sum will be 10 + 7 + 15 = 32and, if the values for L and R are 4 and 15 then the selected nodes will be:
The sum will be 4 + 5 + 7 + 10 + 15 = 41Keep 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 {
return
}
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.
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.
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.
We’ve moved to 7 and add its value to sum.
We move to 15 and add it’s value to sum. We’ll not move to 18 now.
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.