programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Possible recursion issue

Larissa Perkins
Greenhorn
Posts: 17
I have built a binary tree, from a file. In each node, I am storing each word as a string, and an int frequency for each time the word occurs. For the assignment, I need to find how many words occur only once in the file. I wrote the program, but for some reason I am getting a number different from what my professor is expecting.

As far as I know, this file has loaded into the tree correctly, because all of my other answers in the assignment are correct. What am I doing wrong?

Campbell Ritchie
Marshal
Posts: 56598
172
Start by expecting the correct number, and then tell us what happens and what you expected.
Also please explain in words of one syllable (if possible) how you designed that recursion. What sort of tree traversal have you got?

Larissa Perkins
Greenhorn
Posts: 17
I'm not sure what you mean by "expecting". My professor gave us the answer of number of words occurring exactly once, so that we can make sure our program is working correctly. Mine is not, because it is not the same number he gave us.

I believe that I have a pre-order traversal, which I think should be evident from my code.

Paul Clapham
Sheriff
Posts: 22841
43
It looks to me like you're traversing the tree and trying to count the nodes for which "subTree.getFreqCount() == 1" is true, am I right?

I have to say that your idea of passing the "uniqueCount" as a parameter all over the place is rather confusing. My approach would be this: the unique count for a node is 1 if getFreqCount() is 1, plus the unique count for the left subtree, plus the unique count for the right subtree.

Stefan Evans
Bartender
Posts: 1837
10
Nothing seems obviously wrong with the counting unique words in the tree code you have posted.
So if the issue isn't there, then the issue is probably in the code you are using to build up the tree.
Or maybe it's the data

Nah, that last one would never happen...

I do agree with Paul that I would have done it without the 'uniqueCount' parameter. I don't think that will affect your final answer, but the advantage to that approach is that you get interim results to verify it for each subtree.

I am presuming that the input the professor has given you is too large to manually verify his answer.
Maybe try a shorter input where you CAN count and verify the answer and see if you can duplicate the problem on a smaller scale?

If your answer is higher, then you possibly have a duplicate node/word in your tree. So it would count each of those as a single occurrence when in fact it should be one node with an occurence count of 2.
If your answer is lower, then you are missing words, or missing traversing the tree in some fashion.

It comes down to testing your program with various inputs that you know the answer to. How easy is it to set up some unit tests with different inputs to run it on different data?

Putting some logging statements might help you understand where things go wrong. Can you print out your tree?
How about storing/printing out each unique word you come across?

Campbell Ritchie
Marshal
Posts: 56598
172