stack overflow problem in program

Question

So I am currently getting a strange stack overflow exception when i try to run this program, which reads numbers from a list in a data/text file and inserts it into a binary search tree. The weird thing is that when the program works when I have a list of 4095 numbers in random order. However when i have a list of 4095 numbers in increasing order (so it makes a linear search tree), it throws a stack overflow message. The problem is not the static count variable because even when i removed it, and put t=new BinaryNode(x,1) it still gave a stack overflow exception. I tried debugging it, and it broke at if (t == NULL){ t = new BinaryNode(x,count); Here is the insert function.

BinaryNode *BinarySearchTree::insert(int x, BinaryNode *t) {
 static long count=0;
 count++;

 if (t == NULL){ 
  t = new BinaryNode(x,count);
  count=0;
 }
 else if (x < t->key){
  t->left = insert(x, t->left);
 }
 else if (x > t->key){
  t->right = insert(x, t->right);
 }
 else
  throw DuplicateItem();
 return t;
}

Answer 1

In a language like C++, you cannot use recursive algorithms on tall trees because each function call uses additional space on a limited stack. You must either change your algorithm (use iteration rather than recursion) or use a balanced binary tree structure.

If you have a bounded input (as it appears you do in this case), you can relieve stack pressure by either making the stack bigger (as Andreas suggests) or put less data on the stack. It seems as though insert is a member function of the BinarySearchTree class even though it doesn't reference any other members of the class. If you make insert a static method (or a regular function not in a class), it won't have to push a this pointer on the stack for every function call, and you will be able to get more iterations before overflowing.

Answer 2

You can increase the size of the stack. Depending on which compiler you're working with this is done in different ways. For instance in Visual Studio the stack size can be set with the command line option:

/F stacksize