Segmentation error when inserting more than 30,000 elements into a binary search tree

Question

I'm currently working on a program that should generate at least 100,000 URLs (www.google.com.my) and insert them into a binary search tree (BST) and hash tables. I got both of them right, but when I try to insert 100,000 URLs into the BST I get the following: Process returned -1073741571 (0xC00000FD) execution time: 21.358 s. And when I run the debugger I get the following: Program received signal SIGSEGV, Segmentation fault.In ?? () (). The debugger did not show which line the error was, so where is the problem and how do I fix it?

This is my code:

main.cpp

#include <iostream>
#include <ctime>
#include <vector>
#include <stdint.h>
#include <cstdlib>
#include <fstream>
#include <string>
#include <conio.h>
#include <stdexcept>
#include "HashTable.cpp"
#include "BinarySearch.h"

using namespace std;

HashTable<long long> ht(0);
treeNode *root = NULL;

vector<long long> dataList;
bool error_msg = false;
static long long nextIC = 1;
long long getNextIC()
{
    return ++nextIC;
}

.
.
.
.
ifstream file2(fileName);
        while (getline(file2, str))
        {
            root = insertNode(root, countData);
            countData++;
        }
        file2.close();

        end = clock();
        elapsed_secs = double(end - begin) / ( CLOCKS_PER_SEC / 1000);

BinarySearch.h

#include <iostream>
#include <stdlib.h>
#include <conio.h>

using namespace std;

struct treeNode
{
    long long data;
    treeNode *left;
    treeNode *right;
};

treeNode *insertNode(treeNode *node,long long data)
{
    if(node==NULL)
    {
        treeNode *temp = new treeNode();
        temp -> data = data;
        temp -> left = temp -> right = NULL;
        return temp;
    }
    if(data >(node->data))
    {
        node->right = insertNode(node->right,data);
    }
    else if(data < (node->data))
    {
        node->left = insertNode(node->left,data);
    }
    /* Else there is nothing to do as the data is already in the tree. */
    return node;
}

treeNode * searchNode(treeNode *node, long long data)
{
    if(node==NULL)
    {
        /* Element is not found */
        return NULL;
    }
    if(data > node->data)
    {
        /* Search in the right sub tree. */
        return searchNode(node->right,data);
    }
    else if(data < node->data)
    {
        /* Search in the left sub tree. */
        return searchNode(node->left,data);
    }
    else
    {
        /* Element Found */
        return node;
    }
}
void displayInorder(treeNode *node)
{
    if(node==NULL)
    {
        return;
    }
    displayInorder(node->left);
    cout<<" " << node->data<<" ";
    displayInorder(node->right);
}
void displayPreorder(treeNode *node)
{
    if(node==NULL)
    {
        return;
    }
    cout<<" " <<node->data<<" ";
    displayPreorder(node->left);
    displayPreorder(node->right);
}
void displayPostorder(treeNode *node)
{
    if(node==NULL)
    {
        return;
    }
    displayPostorder(node->left);
    displayPostorder(node->right);
    cout<<" " <<node->data<<" ";
}

`0xC00000FD` is the error code for _stack overflow_. Are you going too deep into the recursion, by any chance? — Algirdas Preidžius, Feb 05 '18 at 10:19
[Probably dupe](https://stackoverflow.com/questions/7763959/what-is-unknown-software-exception-0xc00000fd-error-and-how-to-avoid-it). — user202729, Feb 05 '18 at 10:20
You should have said that you're using Windows in the question. — user202729, Feb 05 '18 at 10:21
For the solution, [probably dupe](https://stackoverflow.com/questions/40157847/increase-stack-size-in-c). [Or this](https://stackoverflow.com/questions/156510/increase-stack-size-on-windows-gcc). Please do some research before [asking](https://meta.stackoverflow.com/questions/261592/how-much-research-effort-is-expected-of-stack-overflow-users) on Stack Overflow. — user202729, Feb 05 '18 at 10:22
@user202729 increasing stack size isn't a good solution. It is better to reduce the depth of recursion. — eerorika, Feb 05 '18 at 10:33

score 1 · Answer 1 · answered Feb 05 '18 at 10:32

Trees are limited in their maximum depth i.e. the distance from root to the furthest leaf. This limitation is imposed by the recursive nature of the tree algorithms because recursion depth itself is limited by the size of the stack memory. Recursion depth is limited by the stack space because each function call places a new call frame on the stack.

This maximum depth limitation is a problem for non-balanced BST because such tree can become unbalanced. In the worst case, when elements are inserted in sorted order (or reverse), the depth grows linearly.

To support large number of elements in any insertion order, you can use a balanced BST such as red-black tree or AVL tree. The depth limitation is much less of a problem for balanced trees because their maximum depth grows logarithmically.

(side note: `std::set` is often implemented with red black tree) — user202729, Feb 05 '18 at 10:40

Segmentation error when inserting more than 30,000 elements into a binary search tree

1 Answers1