I am trying to sum the all children values from its node between a specific range from its root node.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Program {
public static class Node {
int data;
List<Node> children;
public Node(int data) {
this.data = data;
children = new ArrayList<>();
}
public void addChildren(Node... children) {
this.children.addAll(Arrays.asList(children));
}
}
public int sumRange(Node root, int min, int max) {
int sum = 0;
if(root.data >= min && root.data <= max) {
sum = root.value;
}
int size = root.children.size();
for (int i = 0; i < size; i) {
if(root.children.get(i).data >= min && root.children.get(i).data <= max) {
sum = sumRange(root.children.get(i), min, max);
}
}
return sum;
}
public static void main(String[] args) {
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node6 = new Node(6);
Node node7 = new Node(7);
Node node2 = new Node(2);
node2.addChildren(node3, node4);
Node node5 = new Node(5);
node5.addChildren(node6, node7);
Node node8 = new Node(8);
Node node1 = new Node(1);
node1.addChildren(node2, node5, node8);
Program program = new Program();
System.out.println(program.sumRange(node1, 3, 5)); // Should print 12
System.out.println(program.sumRange(node2, 3, 5)); // Should print 7
}
}
I have tried this code to calculate the sum of nodes between a specific range:
public int sumRange(Node root, int min, int max) {
int sum = 0;
if(root.data >= min && root.data <= max) {
sum = root.value;
}
int size = root.children.size();
for (int i = 0; i < size; i) {
if(root.children.get(i).data >= min && root.children.get(i).data <= max) {
sum = sumRange(root.children.get(i), min, max);
}
}
return sum;
}
And, its summation correctly the only that nodes which have no children. In this line its the node1 have multiple child and it should calculate only the specific range nodes which should sum result 12. But its printing the sum result 5.
System.out.println(program.sumRange(node1, 3, 5)); // Should print 12
I wants to calculate all the child nodes data also. Any help will be appreciated!
CodePudding user response:
The problem is that you only visit child nodes that are within your range. This means if node2 has value 2 its children are never visited and you cannot sum the values 3 and 4. The solution to your problem is removing the if condition in the loop like this:
public int sumRange(Node root, int min, int max) {
int sum = 0;
if(root.data >= min && root.data <= max) {
sum = root.data;
}
int size = root.children.size();
for (int i = 0; i < size; i) {
sum = sumRange(root.children.get(i), min, max);
}
return sum;
}
If you try again the output should be 12 for node 1.