Win a copy of Succeeding with AI this week in the Artificial Intelligence and Machine Learning forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Paul Clapham
  • Ron McLeod
  • Liutauras Vilda
  • Junilu Lacar
Sheriffs:
  • Tim Cooke
  • Jeanne Boyarsky
  • Knute Snortum
Saloon Keepers:
  • Stephan van Hulst
  • Tim Moores
  • Tim Holloway
  • Carey Brown
  • Piet Souris
Bartenders:
  • salvin francis
  • fred rosenberger
  • Frits Walraven

BST StackOverFlowError for large values

 
Greenhorn
Posts: 14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have written a program [ Inputs: Number of pages in the book, Page number to be searched ] to store book pages [ starting from page number '1' on the right side ] in a binary tree having the following structure:
                                                                     1
                                                                    / \
                                                                   2   3
                                                                       / \
                                                                      4  5
                                                                         / \
                                                                        6  7......
The program computes the number of pages [ nodes ] to be turned, to get the suggested page number, from front[top-bottom] and back[bottom-top]. Return the minimum number of pages to be turned over, to reach the suggested page number. this works fine for small values. However it is throwing StackOverFlow Error while entering large values like NumberOfPages: 37455, PageNumberToBeFound: 29835.
What code changes can I make to avoid this error? I understand the above tree is not a balanced tree but the insertion/page order also should remain intact. Please suggest accordingly.
 
Mary Rani
Greenhorn
Posts: 14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Mary Rani wrote:I have written a program [ Inputs: Number of pages in the book, Page number to be searched ] to store book pages [ starting from page number '1' on the right side ] in a binary tree having the following structure:
                                                                     1
                                                                    / \
                                                                   2   3
                                                                       / \
                                                                      4  5
                                                                         / \
                                                                        6  7......
The program computes the number of pages [ nodes ] to be turned, to get the suggested page number, from front[top-bottom] and back[bottom-top]. Return the minimum number of pages to be turned over, to reach the suggested page number. this works fine for small values. However it is throwing StackOverFlow Error while entering large values like NumberOfPages: 37455, PageNumberToBeFound: 29835.
What code changes can I make to avoid this error? I understand the above tree is not a balanced tree but the insertion/page order also should remain intact. Please suggest accordingly.

 
Saloon Keeper
Posts: 7112
65
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I find this a bit confusing. My concept of a binary tree is one where for a given node, IF it has a node to the left, the data in the left node will be less than the data in the given node. Similarly, IF the given node has a node to the right then the data in the node to the right would be greater than the data in the given node. As such, an unbalanced tree would look like:

Also, can you provide some of the sample data that you are using to test your program with, both working data and failing data?
 
Mary Rani
Greenhorn
Posts: 14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I am sorry if the problem statement was not clear.

For any given numberOfPages, starting with pageNo:1, first node[n1] will have data as '1'. Then the next pageNo i.e. '2' will be populated in left sub-node[n2] of n1. '3' will be loaded in right sub-node[n3] of n1. '4' will be populated in the left node[n4] of n3. '5' will be loaded in the right sub-node[n5] of n3 and so on.
For example, if numberOfPages: 6, pageNo to be found: 4, then the number of pages to turn over/number of levels to traverse to 4/n4, from top-bottom would be 2. From bottom-top, would be 1. Minimum of (2,1) would be '1', which is the final output given by the code.
So for small values it works fine.
When the input values are bigger, like numberOfPages: 37455, pageNo to be found: 29835, the following exception is seen:
Exception in thread "main" java.lang.StackOverflowError
at Solution1.countBookFront(Solution1.java:91)
at Solution1.countBookFront(Solution1.java:91)
at Solution1.countBookFront(Solution1.java:91)
at Solution1.countBookFront(Solution1.java:91)

The loc giving the error is  ' countBookFront(node.right,pageNo,node.data,flag);' inside the method 'public static void countBookFront(Node node, int pageNo, int parent, boolean flag) {.....}
Hope this clarifies the confusion.
 
Carey Brown
Saloon Keeper
Posts: 7112
65
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This is not uncommon with recursion, especially with unbalanced trees of significant depth.

A general premise is that all loop algorithms can be converted into recursive algorithms and vice versa.

You'd need to convert your recursive code into a loop to avoid using the stack. Here's a sample of your code that has been modified:

 
Mary Rani
Greenhorn
Posts: 14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Awesome!!! I have followed your suggestion and replaced the recursive call with loop and voila. All the corner test cases have passed. I searched online, to address the exact problem i.e.

This is not uncommon with recursion, especially with unbalanced trees of significant depth.

. But could not find a proper solution. Thank you. This has cleared some concepts on BST.
 
Carey Brown
Saloon Keeper
Posts: 7112
65
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Or, take a mathematical approach...
 
Mary Rani
Greenhorn
Posts: 14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This was my initial approach. But I wanted to try with BST as well and see if I could have got a workable solution.
 
Saloon Keeper
Posts: 11928
254
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
To reduce the worst case time of your searches from O(n) to O(log n), you may want to implement your tree as a red-black tree.

It will not prevent a StackOverflowError on really large trees when using recursion, but they will be significantly less likely to occur.
 
Wait for it ... wait .... wait .... NOW! Pafiffle! A perfect tiny ad!
Try Free Java/.NET Libraries for Word Excel PowerPoint and PDF
htttp://www.e-iceblue.com/free-apis.html
    Bookmark Topic Watch Topic
  • New Topic