• Post Reply Bookmark Topic Watch Topic
  • New Topic

StackOverFlowError In my Recursive Method  RSS feed

 
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Guys,



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!
 
Sheriff
Posts: 57818
178
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to the Ranch

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?
 
Bartender
Posts: 3864
47
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Any chance that the Nodes of your tree got referenced in a circular fashion?
 
Carey Brown
Bartender
Posts: 3864
47
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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.
 
Campbell Ritchie
Sheriff
Posts: 57818
178
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes, I think I may have been mistaken. Sorry.
 
Carey Brown
Bartender
Posts: 3864
47
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I merged your stuff with the following thread. I hope that is okay by you.
 
LostInCode Coder
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi There,

My method is giving stackoverflow error pointing to the line that I have made bold.
I would really appreciate some help!


 
Rancher
Posts: 3348
38
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What does getLeft() return?
Can you show that code, and the code that populates your Nodes.
 
Ranch Hand
Posts: 67
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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.
 
Marshal
Posts: 5479
377
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
For me would be most interesting to see your class where this all code resides.
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!