CODEWITHSUNDEEP
javabinary-search-treeavl-tree
Paul12596
Paul12596

Reputation: 300

When does StackOverflowError get thrown?

Something that came up in an assignment, and could be due to my potato laptop, but I was interested in when a StackOverflow happens for an unbalanced BST (on purpose).

So I'm comparing the worst performance searching an AVL tree vs unbalanced BST, and the same method that searches for an element works for the AVL, but I get StackOverflow error for the BST. The BST ends up just being a linked list with the "bad data" being fed into it (alphabetical names; around 10000), so at what number of calls to entryExists would it produce that error?

I know the unbalanced BST obviously performs much worse than an AVL at worst case, but I want to limit the search queries to acquire some kind of time number.

[I don't think posting the actual code is necessary, but if anyone needs it, I'll upload it - as far as I can tell, it's not just me doing infinite recursion (same method used for both).]

Upvotes: 0

Views: 63

Answers (1)

Stephen C
Stephen C

Reputation: 719299

A stack overflow happens in a situation where there are too many method calls active (i.e. in progress) on a single thread.

Each method call requires a stack frame to hold the local variables for the call, and some call house-keeping information. (Typically a return address, and a saved top-of-stack pointer.) The stack frames for a thread are held on the thread's stack. This has a fixed size (determined when the thread is created). The default depends on the JVM and the command line switches, but it is typically 1Mbytes.

There are four scenarios which can lead to a stack overflow:

  1. Infinite recursion is guaranteed to lead to stack overflow (unless something else terminates the code first).
  2. Finite recursion that is too deep. For instance, if your code traverse a list recursively, it will most likely overflow the stack is the list is long enough. (The recursion is not infinite.)
  3. Non-recursive code that is complicated and involves a very deep call stack.
  4. Non-recursive code with a call-chain involving methods with a large number of local variables.

Scenarios 3 and 4 are unlikely, but they can be more likely if your threads are created with unusually small thread stacks. (For example, if you are trying to economize on thread stack memory.)

In your case, scenario 2 is your worry. This should not happen if your tree is properly balanced. However if an tree is extremely unbalanced, it can be extremely deep. Combine that with an algorithm which recurses to (say) search the tree, and a deep enough tree can lead to stack overflow.

Note: this is NOT infinite recursion. Rather it is the combination of a recursive algorithm and a data structure that has an unfortunate "shape".

Upvotes: 2

Related Questions