title: Why does Valgrind report memory leaks on Binary Search Tree (BST) still?
body: <pre><code>void DeleteNodes(BTNode* node)
  {
      // Recurse left down the tree...
      if(node-&gt;left != NULL)
      {
          DeleteNodes(node-&gt;left);
      }
      if(node-&gt;right != NULL)
      {
          DeleteNodes(node-&gt;right);
      }
  
  
      // Free memory used by the node itself.
      delete node;
  }
  </code></pre>
  
  <p>This is what Valgrind yells at me.</p>
  
  <pre><code>==20793== Invalid read of size 8
  ==20793==    at 0x407B68: toString(std::string, NodeInterface*) (in /users/guest/j/jnuss2/Desktop/To Students BST/dont_run_me)
  ==20793==    by 0x4081CF: printBST(BSTInterface*) (in /users/guest/j/jnuss2/Desktop/To Students BST/dont_run_me)
  ==20793==    by 0x40856F: printError() (in /users/guest/j/jnuss2/Desktop/To Students BST/dont_run_me)
  ==20793==    by 0x4028E9: main (in /users/guest/j/jnuss2/Desktop/To Students BST/dont_run_me)
  ==20793==  Address 0x4c448b0 is 0 bytes inside a block of size 32 free'd
  ==20793==    at 0x4A07991: operator delete(void*) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
  ==20793==    by 0x407785: BTNode::~BTNode() (in /users/guest/j/jnuss2/Desktop/To Students BST/dont_run_me)
  ==20793==    by 0x407213: DeleteChildren(BTNode*) (in /users/guest/j/jnuss2/Desktop/To Students BST/dont_run_me)
  ==20793==    by 0x4075A7: BST::clear() (in /users/guest/j/jnuss2/Desktop/To Students BST/dont_run_me)
  ==20793==    by 0x402874: main (in /users/guest/j/jnuss2/Desktop/To Students BST/dont_run_me)
  ==20793== 
  pure virtual method called
  terminate called without an active exception
  </code></pre>
  
  <p>I have been debugging this particular bit of code. The program was not reporting these memory leaks before I implemented this piece. I have looked up different Valgrind errors and I understand that Invalid read of size 8 means that it is attempting to access memory that has already been freed (<a href="http://valgrind.org/docs/manual/mc-manual.html" rel="nofollow noreferrer">http://valgrind.org/docs/manual/mc-manual.html</a>). However, I can't figure out where the recursive algorithm is accesing the same memory over and over again. I also found a few other answers to this on StackExchange like this:<a href="https://stackoverflow.com/questions/18886298/valgrind-4-bytes-inside-a-block-of-size-8-freed">Valgrind... 4 bytes inside a block of size 8 free&#39;d</a>.
  It doesn't help in my case because I'm not using double pointers to my knowledge. Anyways, if anymore code is needed i can post, but this is the only one that is giving issue thus far. I can also post the rest of the code in this .cpp file but as far as I can tell its irrelevant because there were no memory leak errors until I put in this code.</p>
  
  <p>Here is the memory report after Valgrind has finished running.</p>
  
  <pre><code>==20793== HEAP SUMMARY:
  ==20793==     in use at exit: 8,953 bytes in 6 blocks
  ==20793==   total heap usage: 2,036 allocs, 2,030 frees, 811,313 bytes allocated
  ==20793== 
  ==20793== 24 bytes in 1 blocks are still reachable in loss record 1 of 6
  ==20793==    at 0x4A06965: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
  ==20793==    by 0x401DC3: main (in /users/guest/j/jnuss2/Desktop/To Students BST/dont_run_me)
  ==20793== 
  ==20793== 26 bytes in 1 blocks are possibly lost in loss record 2 of 6
  ==20793==    at 0x4A06965: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
  ==20793==    by 0x30020BDCF8: std::string::_Rep::_S_create(unsigned long, unsigned long, std::allocator&lt;char&gt; const&amp;) (in /usr/lib64/libstdc++.so.6.0.19)
  ==20793==    by 0x30020BF5B0: char* std::string::_S_construct&lt;char const*&gt;(char const*, char const*, std::allocator&lt;char&gt; const&amp;, std::forward_iterator_tag) (in /usr/lib64/libstdc++.so.6.0.19)
  ==20793==    by 0x30020BF9E7: std::basic_string&lt;char, std::char_traits&lt;char&gt;, std::allocator&lt;char&gt; &gt;::basic_string(char const*, std::allocator&lt;char&gt; const&amp;) (in /usr/lib64/libstdc++.so.6.0.19)
  ==20793==    by 0x40819C: printBST(BSTInterface*) (in /users/guest/j/jnuss2/Desktop/To Students BST/dont_run_me)
  ==20793==    by 0x40856F: printError() (in /users/guest/j/jnuss2/Desktop/To Students BST/dont_run_me)
  ==20793==    by 0x4028E9: main (in /users/guest/j/jnuss2/Desktop/To Students BST/dont_run_me)
  ==20793== 
  ==20793== 32 bytes in 1 blocks are still reachable in loss record 3 of 6
  ==20793==    at 0x4A06965: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
  ==20793==    by 0x407838: Factory::getBST() (in /users/guest/j/jnuss2/Desktop/To Students BST/dont_run_me)
  ==20793==    by 0x401DDA: main (in /users/guest/j/jnuss2/Desktop/To Students BST/dont_run_me)
  ==20793== 
  ==20793== 111 bytes in 1 blocks are possibly lost in loss record 4 of 6
  ==20793==    at 0x4A06965: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
  ==20793==    by 0x30020BDCF8: std::string::_Rep::_S_create(unsigned long, unsigned long, std::allocator&lt;char&gt; const&amp;) (in /usr/lib64/libstdc++.so.6.0.19)
  ==20793==    by 0x30020BE93A: std::string::_Rep::_M_clone(std::allocator&lt;char&gt; const&amp;, unsigned long) (in /usr/lib64/libstdc++.so.6.0.19)
  ==20793==    by 0x30020BE9E3: std::string::reserve(unsigned long) (in /usr/lib64/libstdc++.so.6.0.19)
  ==20793==    by 0x30020BEAA7: std::string::append(std::string const&amp;) (in /usr/lib64/libstdc++.so.6.0.19)
  ==20793==    by 0x408A16: printBeforeError() (in /users/guest/j/jnuss2/Desktop/To Students BST/dont_run_me)
  ==20793==    by 0x4026F3: main (in /users/guest/j/jnuss2/Desktop/To Students BST/dont_run_me)
  ==20793== 
  ==20793== 568 bytes in 1 blocks are still reachable in loss record 5 of 6
  ==20793==    at 0x4A0645D: malloc (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
  ==20793==    by 0x3FFD46C52C: __fopen_internal (in /usr/lib64/libc-2.18.so)
  ==20793==    by 0x300207CA1F: std::__basic_file&lt;char&gt;::open(char const*, std::_Ios_Openmode, int) (in /usr/lib64/libstdc++.so.6.0.19)
  ==20793==    by 0x30020B77F9: std::basic_filebuf&lt;char, std::char_traits&lt;char&gt; &gt;::open(char const*, std::_Ios_Openmode) (in /usr/lib64/libstdc++.so.6.0.19)
  ==20793==    by 0x40853A: printError() (in /users/guest/j/jnuss2/Desktop/To Students BST/dont_run_me)
  ==20793==    by 0x4028E9: main (in /users/guest/j/jnuss2/Desktop/To Students BST/dont_run_me)
  ==20793== 
  ==20793== 8,192 bytes in 1 blocks are still reachable in loss record 6 of 6
  ==20793==    at 0x4A0700A: operator new[](unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
  ==20793==    by 0x30020B71CB: std::basic_filebuf&lt;char, std::char_traits&lt;char&gt; &gt;::_M_allocate_internal_buffer() (in /usr/lib64/libstdc++.so.6.0.19)
  ==20793==    by 0x30020B7811: std::basic_filebuf&lt;char, std::char_traits&lt;char&gt; &gt;::open(char const*, std::_Ios_Openmode) (in /usr/lib64/libstdc++.so.6.0.19)
  ==20793==    by 0x40853A: printError() (in /users/guest/j/jnuss2/Desktop/To Students BST/dont_run_me)
  ==20793==    by 0x4028E9: main (in /users/guest/j/jnuss2/Desktop/To Students BST/dont_run_me)
  ==20793== 
  ==20793== LEAK SUMMARY:
  ==20793==    definitely lost: 0 bytes in 0 blocks
  ==20793==    indirectly lost: 0 bytes in 0 blocks
  ==20793==      possibly lost: 137 bytes in 2 blocks
  ==20793==    still reachable: 8,816 bytes in 4 blocks
  ==20793==         suppressed: 0 bytes in 0 blocks
  </code></pre>