How to recursively add count in java?

Question

I'm using binary search tree to save strings input by user. I wanted to get the total number of strings that matches the range of strings given. However, my current code is unable to add the number of strings correctly.

I'm using recursion to help me count the number of strings that is within the range start and end. For example, it passes through count twice, but my final output is 1 instead of 2. Here is my code:

private int matchQuery(BST T, String START, String END, int count) {
        if (T == null) return count;

        // Go left of tree
        matchQuery(T.left, START, END, count);

        if(T.key != null && withinStartRange(T.key, START)) {
            count++;                       
        }

        // Go right of tree
        return matchQuery(T.right, START, END, count); 
    }

And what does matchQuery do ? Your method is not recursive unless matchQuery is recursive or calls numberOfStrings... but since yo don't provide its code — Dici
– Dici, Commented Aug 30, 2015 at 11:04

Dici · Accepted Answer · 2015-08-30 12:48:16Z

I think the count parameter is useless with Bloodworth approach since he cancels it out every time...

I would go for

private int matchQuery(BST bst, String start, String end) {
    if (bst == null) return 0;

    int count = 0;
    if (bst.key != null && withinRange(bst.key, start, end)) count++; 

    count +=  matchQuery(bst.right, start, end);
    count += matchQuery(bst.left, start, end); 

    return count;    
}

I also fixed a number of details (naming convention etc). This works, however this does not take into account the properties of the data structure. Indeed, when you are on a particular node, you know that all the nodes at its left are lower than it, and all the nodes at its right are higher. Therefore, you can sometimes prevent yourself from exploring some nodes when you know they are out of the range. I assume in he following code that we always have node.left.key < node.key < node.right.key. I also assume that the range is inclusive on both ends

// I assume start <= end has already been checked
private int matchQuery(BST bst, String start, String end) {
    if (bst == null) return 0;
    if (bst.key == null) return matchQuery(bst.left, start, end) + matchQuery(bst.right, start, end);

    int count = 0;

    int compareToStart = bst.key.compareTo(start);
    int compareToEnd = bst.key.compareTo(end);

    if (compareToStart > 0) count += matchQuery(bst.left, start, end);
    if (compareToEnd < 0) count +=  matchQuery(bst.right, start, end);   
    if (compareToStart >= 0 && compareToEnd <= 0) count++;
    return count;    
}

Dici · Accepted Answer · 2015-08-30 12:26:49Z

2

I think the problem might be that you only return the right side of the recursion tree, so if count was increased on the left, it is forgotten. Instead, you could try changing your return statement the following way:

private int matchQuery(BST T, String start, String end, int count) {
    if (T == null) return count;

    if(T.key != null && withinStartRange(T.key, start)) {
        count++;                       
    }

    // Go right of tree
    int rightCount =  matchQuery(T.right, start, end, count);
    // Go left of tree
    int leftCount = matchQuery(T.left, start, end, count); 

    return rightCount + leftCount - count;

}

This should count all increases in "Count". Hope this helps.

Edit: I also subtracted count from the returned amount as the current call's count is counted twice.

Edit2: My suggestion still holds - OP doesn't return the left side of the tree. Changed my code slightly.

edited Aug 30, 2015 at 12:26

Dici

26k7 gold badges45 silver badges86 bronze badges

answered Aug 30, 2015 at 10:44

Bloodworth

1092 silver badges8 bronze badges

4 Comments

Dici Over a year ago

We don't even know what matchQuery does and the method does not seem to be recursive in the question (if matchQuery isn't). You cannot provide an answer at this stage, in my opinion

Bloodworth Over a year ago

Ok, I didn't notice the function header was different - I just assumed the recursive call is matchQuery, so I just corrected the function header.

Dici Over a year ago

I don't see the use of the count parameter here. I think this should be a local variable initialized to 0

Dici Over a year ago

There are quite a lot of problems : START and END are not defined, withinStartRange should probably take a third argument for the end etc

Collectives™ on Stack Overflow

How to recursively add count in java?

2 Answers 2

Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related