Binary search tree destructor: free() invalid pointer

Question

For my current programming assignment I have to construct a binary search tree and use it to insert words from a file in alphabetical order, to make a concordance list. The program is complete and outputs correctly; the main bulk of the program works perfectly. But when the program finishes and destructors are called, it crashes with error in ./concordancebst : free(): invalid pointer. I'm at a loss as to what the problem is, my destructor looks like it would work and looking at code online it seems as though it should work as well. I could probably get around this by using a std::unique_ptr but it seems a bit overkill in the sense of the scope of the program (also overkill in the sense that we haven't covered smart pointers, everything we have done in the class involving dynamic memory has been handled through manual allocating/deallocating).

BST.h

#ifndef BST_H
#define BST_H
#include <string>

class BST {
public:
   BST() { root = nullptr; }
   ~BST();

   void insert(const std::string word);
   int getCount(const std::string word);
   int length();

   friend std::ostream& operator << (std::ostream &out_s, BST b);
private:
   struct Node {
      std::string word;
      int count;
      Node *left;
      Node *right;
      Node() { word = ""; count = 0; left = nullptr; right = nullptr;}
      ~Node();
   };
   Node *root;

   void RInsert(Node* &t, std::string word);
   int countNodes(Node *p);
   void print(Node *p, std::ostream &out_s);
};
#endif

BST.cpp

#include "BST.h"
#include <string>
#include <iostream>
#include <iomanip>

BST::Node::~Node() {
   delete left;
   delete right;
}

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

int BST::countNodes(Node *p) {
   if(p == nullptr)
      return 0;
   else
      return countNodes(p->left) + countNodes(p->right) + 1;
}

int BST::getCount(const std::string word) {
   Node *p = root;
   while(true) {
      if(p == nullptr)
         return 0;
      else if(word.compare(p->word) < 0)
         p = p->left;
      else if(word.compare(p->word) == 0)
         return p->count;
      else
         p = p->right;
   }
}

int BST::length() {
   return countNodes(root);
}

void BST::RInsert(Node* &t, std::string word) {
   if(t == nullptr) {
      t = new Node;
      t->word = word;
      t->left = nullptr;
      t->right = nullptr;
      t->count++;
   }
   else if(word.compare(t->word) == 0)
      t->count++;
   else if(word.compare(t->word) < 0)
      RInsert(t->left, word);
   else //word.compare(t->word > 0)
      RInsert(t->right, word);
}

void BST::insert(const std::string word) {
   RInsert(root, word);
}

void BST::print(Node *p, std::ostream &out_s) {
   if(p != nullptr) {
      print(p->left, out_s);
      out_s << std::setw(13) << p->word << std::setw(10) << p->count <<  std::endl;
      print(p->right, out_s);
   }
}

std::ostream &operator << (std::ostream &out_s, BST b) {
   out_s << std::setw(13) << "Word" << std::setw(10) << "Count" << std::endl;
   out_s << "---------------------------------------------" << std::endl;
   b.print(b.root, out_s);
   out_s << "---------------------------------------------" << std::endl;
   out_s << "The file contains " << b.length() << " distinct words." << std::endl;

   return out_s;
}

[And where is your **`int main()`**](http://stackoverflow.com/help/mcve)? "main" as in "complete". — decltype_auto, Nov 24 '15 at 19:29
Off topic: Save yourself a bit of typing and a clock cycle or two. `Node() { word = ""; count = 0; left = nullptr; right = nullptr;}` can be `Node(): word(""), count(0), left(nullptr), right(nullptr){}` — user4581301, Nov 24 '15 at 19:34
The error, that you told, that you are having mentions `free` function failing. I don't see a `free` function call in the code snippet that you pasted. Are you sure you are showing us the relevant code? On the side note, are you, by any chance, are freeing memory with `free` when that memory was allocated by `new`? — Algirdas Preidžius, Nov 24 '15 at 19:35
@AlgirdasPreidžius good point worth exploring, but deep in the dark underbelly of `delete` one will often find `free`. — user4581301, Nov 24 '15 at 19:42
BST and BST::Node have pointers, constructors and destructors, but no assignment operators. Read ye the Tale of [The Rule of Three](http://stackoverflow.com/questions/4172722/what-is-the-rule-of-three) — user4581301, Nov 24 '15 at 19:43
@decltype_auto I left it out because I thought it wasn't necessary. The crash occurs as main() is exiting, so I thought it wouldn't be needed to post it. @AlgirdasPreidžius `free` is not a function in the code, as @user4581301 it most likely comes from `delete`. — mooles, Nov 24 '15 at 19:56
Two good reasons for the MCVE: it forces the questioner to investigate their code and the problem more deeply. More often than not, building the minimal case exposes the bug and saves the trouble of making the question. Being able to derive minimal code is an important debugging skill, probably right behind using a debugger. Second, the MCVE allows anyone to paste the program code into their IDE of choice and see first hand what the problem is. It removes the guesswork involved in duplicating the test case used by the questioner and the time wasted wondering if the bug is in code not shown. — user4581301, Nov 24 '15 at 20:22
@mooles It's secondary what you *thought* about that. I pointed you to a standing rule of SO. — decltype_auto, Nov 24 '15 at 20:24

score 2 · Accepted Answer · edited Jun 20 '20 at 09:12

2

std::ostream &operator << (std::ostream &out_s, BST b)
                                       Pass by value^. b is copied.

Since BST has no copy constructor, the default copy constructor is invoked and does not perform a deep copy. b contains copies of the source BST's pointers, and when b is destroyed on return from the function, it takes all of the source's Nodes with it to the grave.

Fixes are twofold:

Most directly, pass by reference.

std::ostream &operator << (std::ostream &out_s, BST & b)

Indirectly, this code violates the Rule of Three. BST and BST::Node need copy constructors and assignment operators to be used safely.

Edit

A minimal test case would be something like:

#include <iostream>
#include "BST.h"

int main()
{
    BST t;

    t.insert("A");

    std::cout << t << std::endl;
    return 0;
}

edited Jun 20 '20 at 09:12

Community

1
1

answered Nov 24 '15 at 20:04

user4581301

33,082
7
33
54

Oh, now I understand what you mean by implementing a copy constructor. Now I see it was actually needed in order for the code to work as intended without passing b. My professor never talked about the rule of three so I had no idea, but from now on I'll make sure to follow it. Thank you so much! – mooles Nov 24 '15 at 20:19
Not a problem. Also keep an eye out for the rule of five (basically rule of three with extra methods for handling `std::move`). More good reading here: http://en.cppreference.com/w/cpp/language/rule_of_three – user4581301 Nov 24 '15 at 20:26

Binary search tree destructor: free() invalid pointer

1 Answers1

Edit