Let’s discuss a problem range sum of BST (binary search tree).
In this problem, 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].
Binary Search Tree (BST)
In binary search tree, the value of all the nodes in the left sub-tree is less than the value of the root node. Similarly, Value of all the nodes in the right sub-tree is greater than or equal to the value of the root.
For example
In the below example (image), we have to find the sum of all nodes whose value lies in the range of 7 to 15 (inclusive).
The nodes 7, 10, and 15 lie in this range and its sum is 32.
This is the problem statement. Now let’s discuss how we can solve this problem efficiently.
Range sum of BST video tutorial
Range Sum of BST – Java Code & Explanation
METHOD 1 –
The easiest way to solve this problem is to use any tree traversal algorithm and do the sum of all the nodes that lie in the given range and finally return the sum.
We can use any tree traversal algorithm to solve this problem. In my previous tutorials, I have already covered the tree traversal algorithms.
Binary tree preorder traversal
In this example, I have used in-order traversal to solve this problem. The time complexity of this approach is O(n).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
//Here, I have used inorder traversal class Solution { private int sum = 0; public int rangeSumBST(TreeNode root, int low, int high) { if(root == null) return sum; calculateSum(root, low, high); return sum; } private void calculateSum(TreeNode root, int low, int high) { if(root == null) return; calculateSum(root.left, low, high); if(root.val >= low && root.val <= high) { sum = sum + root.val; } calculateSum(root.right, low, high); } } |
Range Sum of BST LeetCode Solution
In our previous approach, we have visited all the nodes to check whether a node value lies in the given range. We have not used the property of a binary search tree.
Let’s improve our previous solution. Instead of visiting all the nodes, we can check whether the current node value is greater than starting range value then visit the left subtree else skip them. Similarly, check whether the end range is greater than the current node value then visit the right subtree else skip it.
Programming questions on binary search tree
The time complexity of this approach is O(n).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
/* Let's use the property of BST and optimize previous approach. */ class Solution { int sum = 0; public int rangeSumBST(TreeNode root, int low, int high) { if(root == null) return sum; calculateSum(root, low, high); return sum; } private void calculateSum(TreeNode root, int low, int high) { if(root == null) return; if(root.val > low) calculateSum(root.left, low, high); if(root.val >= low && root.val <= high) { sum = sum + root.val; } if(high > root.val) calculateSum(root.right, low, high); } } |
