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
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:
and, if the values for L and R are 4 and 15 then the selected nodes will be:
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 {
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.
- We’ll not traverse the left child of a node if the node’s value is less than L because the all the nodes that are on the left side of a node with value L will always have values less than L.
- Same way, we’ll not traverse the right child of a node if the node’s value is greater than R as all the values will be greater than R in that case.
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.
