Binary Search Tree Implementation C++ Runtime Error

Question

I have a problem when implementing BST in C++. When I insert a small data around 20,000 data to the BST, it runs well. If I try to insert a big number of data around 100,000. The BST get an runtime error. Can you guys help me?

This is my implementation. Binary Search.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 = (treeNode *)malloc(sizeof(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<<" ";
}

I get the run time error at :

node->right = insertNode(node->right,data);

Please do help me guys.

Thank you in advance!

Maybe recursion depth is too big? How large is the per-process stack in your OS? — Erik Alapää, Jan 31 '17 at 12:43
It could simply be that with so many elements you are running out of heap space. Do a search on how to increase your heap size, do it, and then get back to us. — AndyG, Jan 31 '17 at 12:53
Change the recursion to while loop(s). As you are not re-balancing the tree a few 100,000 in-order elements will always blow your stack. Test case: insert 1 to 1,000,000 in sequence. — Richard Critten, Jan 31 '17 at 12:55
What's the error? Have you debugged? Where is the exception thrown? — Luchian Grigore, Jan 31 '17 at 12:59
@P0W Can I know how to fix the memory leaking please? Thank you. — user2672399, Jan 31 '17 at 13:09
@ErikAlapää Can I know how to find the per-process stack in my Windows? Thank you and I'm sorry because I searched the net, but couldn't get it. — user2672399, Jan 31 '17 at 13:10
@user2672399 http://stackoverflow.com/questions/1825964/c-c-maximum-stack-size-of-program — Erik Alapää, Jan 31 '17 at 13:19
@RichardCritten I'm very sorry, but can you explain for about how to change the recursion to while loops? I just don't get it :( — user2672399, Jan 31 '17 at 13:31
@user2672399: Start with a copy of the root node. If inserting, write a while loop that terminates when the node is null. Use your if statements to change the value of the copy. If searching, write a while loop that terminates when the node is null or if data is equivalent. — AndyG, Jan 31 '17 at 20:05
@AndyG I'm very sorry but I don't really know how to change the recursion to while loop. Can you show me a sample? Or can you modify my code above? — user2672399, Feb 03 '17 at 13:07
@user2672399: Something like [this](http://coliru.stacked-crooked.com/a/0dfb3771f897cd8d) — AndyG, Feb 03 '17 at 14:37

score 0 · Answer 1 · answered Feb 03 '17 at 14:42

You're likely running out of stack with all the recursion, so you could either increase the stack, or write some (or all) of your functions to use iteration instead of recursion (although preorder, postorder, inorder traversals are hard to write correctly as loops).

Here's a simple example for the Search and Insert methods:

struct TreeNode
{
    long long data = 0;
    std::shared_ptr<TreeNode> left;
    std::shared_ptr<TreeNode> right;
    TreeNode(long long _data) : data(_data){}
};

class BST
{
    public:
    void Insert(std::shared_ptr<TreeNode> node)
    {
        if (!node)
           throw std::runtime_error("Cannot insert null node");

        if (!root)
        {
           root = node;
           return;
        }

        std::shared_ptr<TreeNode>* next = &root;
        while(*next)
        {
            if (node->data < (*next)->data)
                next = &((*next)->left);
            else
                next = &((*next)->right);
        }
        *next = node;
    }

    std::pair<bool, std::shared_ptr<TreeNode>> Search(long long data)
    {
        if (!root)
           return std::make_pair(false, nullptr); // searching empty tree

        std::shared_ptr<TreeNode> next = root;
        while(next)
        {
            if (data < next->data)
                next = next->left;
            else if (data > next->data)
                next = next->right;
            else
                return std::make_pair(true, next); // match found
        }

        // no match found
        return std::make_pair(false, nullptr);
    }

    private:
    std::shared_ptr<TreeNode> root;
};

A full working demo can be found here

thanks a lot for the demo. It's working perfectly now. Andy, can you help to figure out the Inorder, Preorder and Postorder functions of your code? — user2672399, Feb 04 '17 at 16:08

Binary Search Tree Implementation C++ Runtime Error

1 Answers1