I'm having trouble using the delete operator in C++. I keep getting a "double free or corruption (fasttop)" error when running

Question

void clear() {
  while(1)
  {
    BSTNode<Data> *current = root;
      if(!current)
      {
        return;
      }

    while(current->left)
    {
      current = current->left;
    }

    while(current->right)
    {
      current = current->right;
    }
    delete current;
    current = nullptr;
    //std::cout << current->parent->data << std::endl;
  }
}

So I'm pretty confident I did everything else right with the BST as in sorting, and inserting and what not. If we assume that all that is correct. I am just trying to delete all the nodes in the tree. But i get and error when running through the while loop a second time. I doesn't detect that the current which I thought I delete, is null or not there, so it goes into that pointer again and tries to call delete on it which then gives me the "double free or corruption (fasttop)" error.

*** glibc detected *** ./bst: double free or corruption (fasttop): 0x083770b0 ***
======= Backtrace: =========
/lib/libc.so.6[0x975e31]
/software/common/gcc/lib/libstdc++.so.6(_ZdlPv+0x1f)[0x266b8f]
./bst[0x804976e]
./bst[0x804919a]
./bst[0x8048ff4]
/lib/libc.so.6(__libc_start_main+0xe6)[0x91bd26]
./bst[0x8048981]
======= Memory map: ========
0021f000-002fa000 r-xp 00000000 00:14 3229873    /software/common/gcc-     4.8.1/lib/libstdc++.so.6.0.18
002fa000-002fe000 r--p 000db000 00:14 3229873    /software/common/gcc-4.8.1/lib/libstdc++.so.6.0.18
002fe000-002ff000 rw-p 000df000 00:14 3229873    /software/common/gcc-4.8.1/lib/libstdc++.so.6.0.18
002ff000-00306000 rw-p 00000000 00:00 0
0045c000-0045d000 r-xp 00000000 00:00 0          [vdso]
00752000-00770000 r-xp 00000000 fd:00 42112      /lib/ld-2.12.so
00770000-00771000 r--p 0001d000 fd:00 42112      /lib/ld-2.12.so
00771000-00772000 rw-p 0001e000 fd:00 42112      /lib/ld-2.12.so
00774000-0079c000 r-xp 00000000 fd:00 44717      /lib/libm-2.12.so
0079c000-0079d000 r--p 00027000 fd:00 44717      /lib/libm-2.12.so
0079d000-0079e000 rw-p 00028000 fd:00 44717      /lib/libm-2.12.so
00905000-00a96000 r-xp 00000000 fd:00 42155      /lib/libc-2.12.so
00a96000-00a98000 r--p 00191000 fd:00 42155      /lib/libc-2.12.so
00a98000-00a99000 rw-p 00193000 fd:00 42155      /lib/libc-2.12.so
00a99000-00a9c000 rw-p 00000000 00:00 0
00b20000-00b3b000 r-xp 00000000 00:14 3229870    /software/common/gcc-4.8.1/lib/libgcc_s.so.1
00b3b000-00b3c000 rw-p 0001a000 00:14 3229870    /software/common/gcc-4.8.1/lib/libgcc_s.so.1
08048000-0804d000 r-xp 00000000 00:1a 31125426   /home/linux/ieng6/cs100w/bhn013/P1/bst
0804d000-0804e000 rw-p 00004000 00:1a 31125426   /home/linux/ieng6/cs100w/bhn013/P1/bst
08377000-08398000 rw-p 00000000 00:00 0          [heap]
b77d1000-b77d4000 rw-p 00000000 00:00 0
b77ec000-b77ef000 rw-p 00000000 00:00 0
bfa01000-bfa17000 rw-p 00000000 00:00 0          [stack]
Aborted (core dumped)

This is the full error message.

That's pretty much it... I am calling clear with these few lines of code:

virtual ~BST() {
clear();
}

I haven't the slightest clue as to how to approach this.

Answer 1

current = nullptr; this line doesn't do anything. It changes a local variable which immediately falls out of scope.

In the next iteration, you will find the same node again, but you freed (delete) it, so accessing it is undefined behaviour.

You want to update the pointer to this node in the BST to nullptr.

Answer 2

If you are simply trying to free the tree, then simply do

void clear() {
    delete root;
    root = nullptr;
}

The destructor for BST() should just delete left and right. Recursion will take care of the rest.

Answer 3

The variable "current" is defined inside the while (1) {} block, and is initialized at each iteration through the loop with the value of "root", so the first time through the loop, you delete the left/right branches and then you delete the "root", setting current == nullptr. However, you then repeat the loop and re-define current back to the value of "root" again. This causes you to attempt to delete the branches and "root" all over again, a double free.

Move the definition of "current" outside of the while(1) loop. Or better yet, remove the while(1) loop as its not needed, you always exit on one iteration.

Answer 4

while(current->left || current->right)
{
  if(current->left)
  {
    current = current->left;
  }
  else if(current->right)
  {
    current = current->right;
  }
}
delete current;

I guess this part performs the deletion process iteratively