1

As part of an assignment, I've created a set of utilities for working with binary search trees. Problem is, my binary tree insertion function seems to be leaking, according to Valgrind.

I don't really see where the problem could be, as I compared my algorithm with many found on the web. They all seem to do the same in the same way.

struct rep_binary
{
    info_t data;
    rep_binary*izq;
    rep_binary*der;
};

typedef rep_binary *binary_t ;

static binary_t newNode(info_t i)
{
    binary_t b = new rep_binary;
    b->dato = i;
    b->der = b->izq = NULL;
    return b;
}
binary_t insert_on_binary(info_t i, binario_t b)
{
    assert(binary_empty(find_subtree(info(i), b)));

    if (binary_empty(b))
    {
        b = newNode(i);
    }
    else
    {
        if (strcmp(info(b->data), info(i)) > 0)
            b->left= insert_on_binary(i, b->left);
        else
            b->right= insert_on_binary(i, b->right);
    }

    return b;
}

The output of the function is correct, meaning when I print the outcome trees I get exactly what you'd expect after inserting x nodes. However, Valgrind reports I'm losing 12 bytes per insertion for some reason.

For instance, there's a method that creates a BST from a linked list that has 39 elements, and after inserting those 39 elements I lose 468 bytes (39*12).

Same happens with all other methods that rely on inserting to a BST to function.

As a side note, when diffing my outcomes with the ones of the assignment, there are no differences whatsoever. So it works, but leaks somewhere?

fdk1342
  • 3,274
  • 1
  • 16
  • 17
Seba ventura
  • 19
  • 3
  • `valgrind` probably reports a leak because this example doesn't free any of the allocated memory. https://stackoverflow.com/questions/5134891/how-do-i-use-valgrind-to-find-memory-leaks – fdk1342 Apr 22 '19 at 17:43
  • @Fred I failed to mention the driver program that ultimately executes my functions frees all trees and linked lists before finishing. I would otherwise agree that's definitely the problem. You did give me an idea though, maybe I'm messing somewhere and creating a bst/list the driver program has no reference about, thus not being able to clean after it. – Seba ventura Apr 22 '19 at 18:25

0 Answers0