How do I correct c++ memory leaks with my binary search tree pointers?

Question

I'm applying some operations to some data structures on C++. I read the operations from a CSV file, calculate CPU time, and write it to another CSV file.

I'm doing this for hundreds of sets of operations, however, after several applications of make_experiment(), I get the following error:

terminate called after throwing an instance of 'St9bad_alloc' what(): std::bad_alloc

Apparently it may be because for some reason I ran out of memory. What could be going wrong? ABB is a BST.

Here's the code:

#include <iostream>
#include <string>
#include <fstream>
using namespace std;
typedef unsigned int uint;

string PATH_IN = "ops/";

struct node{
    uint data;
    node* left;
    node* right;
};

class ABB{
    private:
        node* root;
        node* insert(uint x, node* t);
        int find(node* t, uint x);

    public:
        ABB();
        void insert(uint x);
        int search(uint x);
};

node* ABB::insert(uint x, node* t){
    if (t == NULL){
        t = new node;
        t->data = x;
        t->left = t->right = NULL;
    }
    else if(x < t->data)
        t->left = insert(x, t->left);
    else if(x > t->data)
        t->right = insert(x, t->right);
    return t;
}

int ABB::find(node* t, uint x){
    if(t == NULL)
        return 0;
    else if(x < t->data)
        return find(t->left, x);
    else if(x > t->data)
        return find(t->right, x);
    else
        return 1;
}

ABB::ABB() {
    root = NULL;
}

void ABB::insert(uint x) {
    root = insert(x, root);
}

int ABB::search(uint x) {
    return find(root, x);
}

void make_experiment(string tree_type, string exp_type, int n){

    // Declaration of variables
    ABB abb;
    ifstream file_in;
    ofstream file_out;
    string line;
    string op;
    string sval;
    uint val;
    int found;

    // Opening input and output files
    if(exp_type == "r"){
        file_in.open(PATH_IN + "random/random_" + to_string(n+1) +  ".csv");
    }
    file_out.open(tree_type + "_" + exp_type + "_" + to_string(n+1) + ".csv");

    // Dealing with headers
    getline(file_in, line);
    file_out << "op,time_ms" << endl;

    // Applying operations and writing elapsed time to output CSV
    while(getline(file_in, op, ',')) {
        file_out << op << ","; 
        getline(file_in, sval);
        val = (uint)stoul(sval);
        if(op == "i"){
            if(tree_type == "abb"){
                abb.insert(val);
            }
        }
        else if(op == "be"){
            if(tree_type == "abb"){
                found = abb.search(val);
            }    
        }
        else{
            if(tree_type == "abb"){
                found = abb.search(val);
            }
        }
        file_out << "time_elapsed" << endl; 
    }
    file_in.close();
    file_out.close();
}

int main(){
    for(int i=0; i<1000; i++){
        make_experiment("abb", "r", i);
        cout << "ww" << endl;
    }
    return 0;
}

Input CSV files look like this, with a million rows:

operation,value
i,771383893
be,4071986422
i,2493790208
bi,297183474

Usually it works until i≈250, correctly creating the corresponding output files, and then the error comes.

Answer 1

The most probable cause is that fact that you create and allocate a raw pointer in your private insert function:

node* ABB::insert(uint x, node* t){
    if (t == NULL){
        t = new node; //< new pointer created
        //...
    }
    //...
}

then pass it to your root data member in your public version of insert:

void ABB::insert(uint x) {
    root = insert(x, root);
}

but then don't ever destroy/deallocate the root member pointer when you're done (i.e. when an ABB object is destroyed).

The easiest way to correct this is to delete the root pointer in ABB's destructor (which you would explicitly declare and define):

ABB::~ABB(){
   delete root;
}

Similarly, you need a destructor for node, so that every node's left and right pointer gets recursively freed, otherwise all the BST leaves will still have memory leaks (note that there's multiple ways to implement this, mine is a very basic example implementation; you should look into an implementation that suits your needs the best):

node::~node() {
    delete left;
    delete right;
}

You can use std::couts or your debugger to visually see how these destructors work

I would also look into completely reworking the design (specifically the private insert function and maybe even the private find function) to not have to allocate and pass raw pointers in a separate function, because, though unlikely, memory can leak if something like an exception occurs while root is still being assigned:

node* ABB::insert(uint x, node* t){
    if (t == NULL){
        t = new node;
        t->data = x;
        t->left = t->right = NULL;
    }
    else if(x < t->data)
        t->left = insert(x, t->left);
    else if(x > t->data)
        t->right = insert(x, t->right);
    return t; //< exception occurs somewhere in the function before this line
}
void ABB::insert(uint x) {
    root = insert(x, root); //< root is never assigned; t is still allocated but not freed
}

More importantly, if you somehow end up using the private insert function somewhere else in your program, you may forget to delete that specific pointer and have the same problem all over again. This won't be a problem if your insert doesn't return a raw pointer.

An even better solution (if you have C++11 or newer) is to rework the design to use smart pointers such as std::unique_ptr instead of raw pointers, since smart pointers have built in RAII and will manage the pointer de-allocation for you:

struct node{
    uint data;
    std::unqiue_ptr<node> left;
    std::unqiue_ptr<node> right;
    //Destructor no longer needed in this minimal example
};

class ABB{
    private:
        std::unqiue_ptr<node> root;
        std::unqiue_ptr<node> insert(uint x, node& t);
        int find(node& t, uint x);
    public:
        //No destructor or contructor needed in the minimal example
        void insert(uint x);
        int search(uint x);
};