binary search tree delete causing errors
<p>I'm currently working on an implementation of A Binary Search Tree but I'm getting errors when I try to delete a node with double child. It's not seg faulting though. the error causes an abort at</p>

<pre><code>delete curr
</code></pre>

<p>So what I mean is that it makes it all the way down the cases and through the reassigning of nodes and then when I try to delete it aborts. Ideas? here's my BST implementation</p>

<p>Edit: Error occurs after </p>

<pre><code>cout &lt;&lt; "here2" &lt;&lt; endl;
</code></pre>

<p>in Delete</p>

<pre><code>#ifndef CTREE_H
#define CTREE_H

#include &lt;iostream&gt;

template&lt;class T&gt; class CTree
{
public:
CTree() {m_root = 0;}
~CTree() {delete m_root;}

//
// class Node
// The nested node class for objects in our tree.
//

class Node 
{
public:
    friend class CTree;

    Node() {m_ll = 0;  m_rl = 0;m_active = true;}
    Node(const T &amp;t) {m_payload = t;  m_ll = 0;  m_rl = 0;}
    ~Node() {delete m_ll;  delete m_rl;}

    T &amp;Data() {return m_payload;}
    const T &amp;Data() const {return m_payload;}

private:
    Node    *m_ll;
    Node    *m_rl;
    T       m_payload;

bool m_active;
};
/********************
/********************
 *
 * Insert an element
 *
 * ******************/
void Insert(const T &amp;t) {

    Node * tree = new Node;

    Node * parent = new Node;

    tree-&gt;m_payload = t;
    if(m_root == NULL){
//      cout &lt;&lt; "creating root" &lt;&lt; endl;
            m_root = tree;

        tree-&gt;m_ll=tree-&gt;m_rl = NULL;
    }
    else{

//      cout &lt;&lt; "else insert" &lt;&lt; endl;
        Node * curr;

        curr = m_root;

        while(curr){

            parent = curr;

            if(tree-&gt;Data() &gt; curr-&gt;Data())

                curr = curr-&gt;m_rl;

            else
                curr = curr-&gt;m_ll;
        }

        if (tree-&gt;Data() &lt; parent-&gt;Data())

            parent-&gt;m_ll = tree;

        else

            parent-&gt;m_rl = tree;
}

}
/**************************************
*
* put data from tree in preorder form
*
***********************************/
void Preorder(std::ostream &amp;p_str) {
    Node * curr = new Node;

curr = m_root;

preorder(curr, p_str);

}
/***********************
*
* Find Depth of Tree
*
* ********************/
int Depth() {
    Node * curr = new Node;

curr = m_root;


int depth  = maxdepth(curr);
}

/*****************************
 *
 * find node with given payload
 *
 * ***************************/

const Node *Find(const T &amp;t) const {}
Node *Find(const T &amp;t) {

    Node * curr = new Node;

Node * parent = new Node;

curr = m_root;

bool flag = false;

while(curr != NULL) //if empty it will just skip this step
{
    if(curr-&gt;Data() == t){

        flag = true; //found

        break;
    }
    else{
        parent = curr;

        if( curr-&gt;Data() &lt; t) {

            curr = curr-&gt;m_rl;
        }

        else{

            curr = curr-&gt;m_ll;
        }
    }
}

if(flag == true){

    return curr;

}
else{

    Node * temp = new Node;

    temp = NULL;

    return temp; //not found return blank node
}
}

/****************************
   *
* Delete an element without loss of parents
*
* ************************/

void Delete(const T &amp;t)
{

    Node * curr = new Node;

Node * parent = new Node;

curr = m_root;

bool flag = false;

while(curr != NULL) //if empty it will just skip this step
{
    if(curr-&gt;Data() == t){

        flag = true; //found

        break;
    }
    else{
        parent = curr; //set new parent

        if( curr-&gt;Data() &lt; t) {

            curr = curr-&gt;m_rl; //traverse right
        }

        else{

            curr = curr-&gt;m_ll; //traverse left
        }
    }
}
if(curr != NULL){

    //delete single leaf node
    if(curr-&gt;m_ll == NULL &amp;&amp; curr-&gt;m_rl == NULL){

        if(parent-&gt;m_ll == curr){

            delete curr;

            parent-&gt;m_ll = NULL;

            return;
        }
        else{
            delete curr;

            parent-&gt;m_rl = NULL;

            return;
        }
    }
    //single child
    if((curr-&gt;m_ll == NULL &amp;&amp; curr-&gt;m_rl != NULL) || ((curr-&gt;m_ll == NULL &amp;&amp; curr-&gt;m_rl != NULL))){


        //curr is left node of parent
        if(parent-&gt;m_ll == curr){

            parent-&gt;m_ll = curr-&gt;m_rl;

            delete curr;

            return;

        }
        //curr is right node of parent
        else{

            parent-&gt;m_rl = curr-&gt;m_rl;

            delete curr;

            return;

        }
    }
    //two children 
    if((curr-&gt;m_ll != NULL &amp;&amp; curr-&gt;m_rl != NULL)){
        cout &lt;&lt; "two children" &lt;&lt; endl;
    //two cases curr is m_ll of parent and curr is m_rl of parent
        if(parent-&gt;m_ll == curr){
            cout &lt;&lt; "left child" &lt;&lt; endl;
            //check if curr-&gt;m_rl has child node if not, easy
            if(curr-&gt;m_rl-&gt;m_rl == NULL){
                //good
                cout &lt;&lt; "Good" &lt;&lt; endl;
                parent-&gt;m_ll = curr-&gt;m_rl;
                cout &lt;&lt; "here" &lt;&lt; endl;
                curr-&gt;m_rl-&gt;m_ll = curr-&gt;m_ll;
                cout &lt;&lt; "here2" &lt;&lt; endl;
                delete curr;

                return;
            }
            else{
                Node * temp = new Node;

                temp = curr-&gt;m_rl;

                //find least child of curr's left child
                while(temp-&gt;m_ll != NULL){

                    temp = temp-&gt;m_ll;
                }

                //connect temp to curr's left child

                temp-&gt;m_ll = curr-&gt;m_ll;

                parent-&gt;m_ll = temp;

                return;
            }
        }
    }
        else{
        //check if curr-&gt;m_ll has child node if not, easy
            if(curr-&gt;m_ll-&gt;m_rl == NULL){
                //good
                parent-&gt;m_rl = curr-&gt;m_ll;

                curr-&gt;m_ll-&gt;m_rl = curr-&gt;m_rl;  

                delete curr;
            }
            else{
                Node * temp = new Node;

                temp = curr-&gt;m_ll;

                while(temp-&gt;m_rl != NULL){

                    temp = temp-&gt;m_rl;

                }

                temp-&gt;m_rl = curr-&gt;m_rl;

                parent-&gt;m_rl = temp;
            }
    }
}
else{ 
//  cout &lt;&lt; "No Node found " &lt;&lt; endl;
    return;
}

}
</code></pre>

<p>I'm going to include my driver and my output</p>

<p>Driver:</p>

<pre><code>using namespace std;

#include &lt;iostream&gt;

#include "Tree.h" 

int main(){

CTree&lt;int&gt; x;

x.Insert(4);
x.Insert(5);
x.Insert(3);
x.Insert(40);
x.Insert(35);
x.Insert(37);
x.Insert(34);

x.Preorder(cout);

x.Delete(35);

x.Preorder(cout);

}
</code></pre>

<p>Output from driver:</p>

<pre><code>4 3 5 40 35 34 37 two children
left child
Good
here
here2
*** glibc detected *** a.out: double free or corruption (fasttop): 0x00000000016d6190     ***
======= Backtrace: =========
lib/libc.so.6(+0x71e16)[0x7f33efa75e16]
/lib/libc.so.6(cfree+0x6c)[0x7f33efa7ab8c]
a.out[0x401179]
a.out[0x40118e]
 a.out[0x401012]
a.out[0x400aac]
 /lib/libc.so.6(__libc_start_main+0xfd)[0x7f33efa22c8d]
  a.out[0x4008f9]
  ======= Memory map: ========


 Abort
</code></pre>
