B+Tree Node sum

Question

I am trying to sum all the elements of a B+ Tree Node at a certain Depth.

Here is the code:

public static int printSumAtD(BTreeNode T, int d) {

    if(d == 0) {
        int sum;

        for (int i = 0; i < T.key.length; i++) {
             sum =  sum + T.key[i];
        }
        return sum;

    } else {
        if(T.isLeaf)
            return 0;
        else{
            for(int i = 0; i < T.n+1; i++) {
                printSumAtD(T.c[i], d-1);
            }
        }
    }

    return 0;

}

The problem is that "sum" would be the sum of each element, however at the end it goes to 0.

Any ideas?

Answer 1

A number of suggestions for you:

1. in recursive calls you need to consider how you will take the results and reduce them. In your case you are ignoring the return value of the recursive calls.

2. This method should really be inside the BTreeNode class so that you can avoid access instance variables key and c (which should be private and have better names).

3. Get used to using Stream and collections for this type of iterative operation rather than traditional iteration.

Putting all that together:

class BTreeNode {
    private int value;
    private List<BTreeNode> children;

    public int sumAtDepth(int depth) {
        if (depth == 0)
            return value;
        else if (depth > 0)
            return children.stream()
                .mapToInt(c -> c.sumAtDepth(depth - 1)).sum();
        else
            throw new IllegalArgumentException("Negative depth");
    }
}