• Post Reply Bookmark Topic Watch Topic
  • New Topic

Possible recursion issue  RSS feed

 
Larissa Perkins
Greenhorn
Posts: 17
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Or maybe your professor's answer is wrong

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?


Is your answer higher or lower than the "expected" answer?
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Sorry for delay in replying.

Yes, it does look like a preorder traversal. What I would do to collect counts in a tree (but other people would do something different) is something like this method (in the Node class)Note you do need the () because the ?: operator has such a low precedence. Also I am here using an inorder traversal. And the count is different from what you want. You cna probably get what you want by changing the logic in line 5 only.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!