Unknown Segementation Fault
<p>I am having a problem in my code. I have run and debugged it several times. It seems to work fine if I do not throw an exception in my getEntry function. But when I do throw an exception, my program has a segmentation fault after that. When I debug through the program, it seems that the nextNodePtr in the getEntryHelper is not 0x0. So it somehow gets changed after it throws the exception and I have no idea why.</p>

<p>My main:</p>

<pre><code>#include &lt;iostream&gt;
#include "BinarySearchTree.h"

int main {
BinarySearchTree&lt;std::string,std::string&gt; myTree;
    myTree.add("book");
        myTree.add("encyclopedia");
    myTree.add("automobile");
    myTree.add("zebra");
        myTree.getEntry(zebra);
        myTree.getEntry(xylophone);
        myTree.getEntry(tree); // Does not get to here

}
</code></pre>

<p>Here are my add an and getEntry methods (although it appears that my getEntry is the problem:</p>

<pre><code>template&lt;typename KeyType, typename ItemType&gt;
void BinarySearchTree&lt;KeyType,ItemType&gt;::add(const ItemType&amp; newEntry) {
    if(rootPtr == NULL)
        rootPtr = new BinaryNode&lt;ItemType&gt;(newEntry);
    else {
        addHelper(rootPtr,rootPtr,newEntry);
    }
}

template&lt;typename KeyType, typename ItemType&gt;
ItemType BinarySearchTree&lt;KeyType,ItemType&gt;::getEntry(const KeyType&amp; aKey) const
        throw(NotFoundException) {
    try {
        BinaryNode&lt;ItemType&gt;* temp = getEntryHelper(rootPtr,aKey);
        std::cout &lt;&lt; temp-&gt;getItem() &lt;&lt; "\n";
        return temp-&gt;getItem();
    }
    catch(NotFoundException&amp; nf) {
        std::cout &lt;&lt; nf.what();
    }
}

template&lt;typename KeyType, typename ItemType&gt;
void BinarySearchTree&lt;KeyType,ItemType&gt;::addHelper(BinaryNode&lt;ItemType&gt;* prevNodePtr,
                                                    BinaryNode&lt;ItemType&gt;* nextNodePtr,
                                                    const ItemType&amp; newEntry) {

    if(nextNodePtr == NULL) { // Base Case
        nextNodePtr = new BinaryNode&lt;ItemType&gt;(newEntry,NULL,NULL);
        if(newEntry &lt; prevNodePtr-&gt;getItem())
            prevNodePtr-&gt;setLeftChildPtr(nextNodePtr);
        else
            prevNodePtr-&gt;setRightChildPtr(nextNodePtr);
        return;
    }
    if(newEntry &lt; nextNodePtr-&gt;getItem()) {
        prevNodePtr = nextNodePtr;
        nextNodePtr = nextNodePtr-&gt;getLeftChildPtr();
        addHelper(prevNodePtr,nextNodePtr,newEntry);
    }
    else {
        prevNodePtr = nextNodePtr;
        nextNodePtr = nextNodePtr-&gt;getRightChildPtr();
        addHelper(prevNodePtr,nextNodePtr,newEntry);
    }
}

template&lt;typename KeyType, typename ItemType&gt;
BinaryNode&lt;ItemType&gt;* BinarySearchTree&lt;KeyType,ItemType&gt;::getEntryHelper(BinaryNode&lt;ItemType&gt;* nextNodePtr,const KeyType&amp; aKey) const {
    if(nextNodePtr == NULL) {
        throw NotFoundException("does not exist in tree.\n");
    }
    else if(nextNodePtr-&gt;getItem() == aKey)
        return nextNodePtr;
    else if(aKey &lt; nextNodePtr-&gt;getItem()) {
        getEntryHelper(nextNodePtr-&gt;getLeftChildPtr(),aKey);
    }
    else {
        getEntryHelper(nextNodePtr-&gt;getRightChildPtr(),aKey);
    }
}
</code></pre>

<p>Output:
automobile
book
encyclopedia
zebra
zebra
Precondition Violated Exception: xylophone does not exist in tree.
Segmentation fault (core dumped)</p>
