sum of nodes in the given range of a BST
public class RangeSumOfBST {
public static class Node {
int data;
Node left, right;
Node(int data) {
this.data = data;
}
}
public static Node insert(Node root, int val) {
if (root == null) {
root = new Node(val);
return root;
}
if (root.data > val) {
root.left = insert(root.left, val);
} else {
root.right = insert(root.right, val);
}
return root;
}
public static int findRangeSum(Node root, int low, int high) {
if (root == null) {
return 0;
}
int sum = 0;
if (low <= root.data && high >= root.data) {
sum += root.data;
}
if (high > root.data) {
sum += findRangeSum(root.right, low, high);
}
if (low < root.data)
{
sum += findRangeSum(root.left, low, high);
}
return sum;
}
public static void inorder(Node root) {
if (root == null) {
return;
}
inorder(root.left);
System.out.print(root.data + " ");
inorder(root.right);
}
public static void main(String[] args) {
int val[] = { 8, 3, 5, 6, 20, 11 };
Node root = null;
for (int i = 0; i < val.length; i++) {
root = insert(root, val[i]);
}
inorder(root);
System.out.println();
System.out.println("sum of nodes in the range between low and high: "+findRangeSum(root, 4, 15));
}
}
Comments
Post a Comment