Above is my method Count, which returns the number of occurrences of a particular Node in the Binary Search Tree.
I am getting StackOverFlowError in line return CountHelper, the last line of the second method highlighted bold.
I would really appreciate some help. Thank you!
You can't use bold tags inside code tags; they don't work.
There is something wrong with trying to iterate a tree going both right and left simultaneously. What you are doing is putting two recursive calls onto the stack for the price of one. You are not taking them off the stack until later, so there is a risk of your having one stack frame for every element in your tree. I would suggest you try one of the traversals visiting one node at a time: that way there won't be more stack frames than the maximum depth of your tree. I don't think it matters whether you do a breadth search or depth (inorder, preorder or postorder); I think they will all require similar time and memory.
But why are you visiting the whole of the tree? If it is a binary search tree, why don't you do a binary search and find the element you are looking for? If it is a binary search tree, will it have more than one element of a particular value in the first place?
Campbell Ritchie wrote:There is something wrong with trying to iterate a tree going both right and left simultaneously. What you are doing is putting two recursive calls onto the stack for the price of one. You are not taking them off the stack until later, so there is a risk of your having one stack frame for every element in your tree.
I'm not sure I agree with this. The outer stack frame for the call to helper would be set up but not called yet. As the parameter of it are gathered (left to right) then a stack is set up for the inner call to the helper and that stack is executed. The net result is that right nodes get visited first but only when those return will the left node be executed. Not the way I'd write it but it looks like it should work, hence my suspicion that the tree somehow connected the nodes in a circular fashion.
LostInCode Coder wrote:Hi There,
My method is giving stackoverflow error pointing to the line that I have made bold.
I would really appreciate some help!
It means search.getLeft() never returns null for some node.
Put a break on lihne 23; see if it ever gets executed at all. If it doesn't then you can suspect the node is defined in some way such that getLeft never returns null and it's defect in the definition of node.
If that doesn't help and you have some idea of the depth of the root node, then add the followihng two statements and two variables.
The first statement is just before line 22. Let it increment and print out a static counter named "numberOfLeftCalls" which is also the first static variable to add to the class definition.
The second statement is just before line 25. Let it increment and print out a static counter named "numberOfRightCalls" which is also the second static variable to add class definition.
Now you can set uyp a conditional break in the debugger that breaks when one of the static variables is way too big to fit your data. WHn it breaks, you know you've got your suspect node that never stops going left (or maybe right ). Have a look at that node, it will probably tell you something.
Also the printlns to sc reen wil give you a big hint about what's going on.
Redursion can have very subtle bugs, as you're discovering.