Binary tree class creating random node, breaking
<p>So I'm implementing a templated binary tree dictionary as a class that inherits from an abstract Dictionary class, and I have a problem with my add function that I can't figure out. </p>

<p>Basically, my tree has nodes that have both a key and value, and pointers to its parent, left child, and right child. The code for the node is</p>

<pre><code>struct bNode {
    K key;
    V value;
    bNode* left;
    bNode* right;
    bNode* parent;
};
</code></pre>

<p>(I know using shared_ptr is better than raw pointers but it wasn't required for this project)
The tree also has a member pointer <code>bNode* root</code>.</p>

<p>To test my tree, I add elements to it and call display after each one. So far, displaying an empty list works properly, as does displaying a list with one element and with two elements.
When I add a third, though, and call display, it breaks...</p>

<p>Here's the code for the add function</p>

<pre><code>void add(K key, V value) override {
    // if list is empty, create new root node
    if (!root){
        root = new bNode;
        root-&gt;key = key;
        root-&gt;value = value;
        return;
    }
    bNode* node = root;
    // travel down tree, checking each node on the way
    while (true){
        // if node exists with passed-in key, change value to passed-in value
        if (node-&gt;key == key){
            node-&gt;value = value;
            return;
        }
        // if key &lt; or &gt; node and node has a left / right child, travel left / right branch
        // if node doesn't have a left / right child, create one and pass in key
        if (key &lt; node-&gt;key){
            if (node-&gt;left){
                node = node-&gt;left;
            } else {
                node-&gt;left = new bNode;
                node-&gt;left-&gt;parent = node;
                node-&gt;left-&gt;key = key;
                node-&gt;left-&gt;value = value;
                return;
            }
        } else {
            if (node-&gt;right){
                node = node-&gt;right;
            } else {
                node-&gt;right = new bNode;
                node-&gt;right-&gt;parent = node;
                node-&gt;right-&gt;key = key;
                node-&gt;right-&gt;value = value;
                return;
            }
        }
    }
}
</code></pre>

<p>here's display</p>

<pre><code>void display() const override {
    if (!root){
        return;
    }
    displayHelper(root);
    cout &lt;&lt; endl;
}
</code></pre>

<p>and here's displayHelper</p>

<pre><code>void displayHelper(bNode* node) const {
    cout &lt;&lt; "(" &lt;&lt; node-&gt;key &lt;&lt; ", " &lt;&lt; node-&gt;value &lt;&lt; ") ";
    if (node-&gt;left){
        cout &lt;&lt; "displaying left... &lt;" &lt;&lt; node-&gt;key &lt;&lt; "&gt; ";
        displayHelper(node-&gt;left);
    }
    if (node-&gt;right){
        cout &lt;&lt; "displaying right... &lt;" &lt;&lt; node-&gt;key &lt;&lt; "&gt; ";
        displayHelper(node-&gt;right);
    }
}
</code></pre>

<p>The lines that cout "displaying right" and "displaying left" were my attempts to bugfix, as it shouldn't run unless the function is about to display another node. This all worked as expected after displaying the first 2 nodes; however, at the third node, it would display that element, and then print "displaying left &lt;*3rd node's key>...", then crash and give me a segmentation fault.</p>

<p>As far as I can tell, this means that for some reason the code is running as if the third added node, which should be a leaf node, actually has children, but then crashing when it tries to read the member variables for nonexistant nodes.</p>

<p>I can't figure out what's causing the bug, as this is all pretty simple code! Any help would be greatly appreciated!</p>

<p>EDIT:
here's an example snippet of code demonstrating the problem;</p>

<pre><code>BSTDictionary&lt;string, int&gt; t;
t.display();
t.add("e", 5);
t.display();
t.add("b", 20);
t.display();
t.add("c", 12);
t.display();
return 0;
</code></pre>

<p>when run, the output looks like</p>

<p>(e,5)</p>

<p>(e,5) displaying left... (e) (b,20)</p>

<p>(e,5) displaying left... (e) (b,20) displaying right... (b) (c,12) displaying left... (c)</p>

<p>Process returned -1073741819 (0xC0000005)  execution time : 1.993 s</p>

<p>There should be no left child of the node containing (c,12), yet the compiler is trying to run as if there is.</p>