BinaryTree Insert Method
<p>For class I have to create a binaryTree and I can't seem to get the insert method to work properly.</p>

<p>Expected results:</p>

<pre><code>first: tree is not empty
        no of nodes    = 15
        height of tree =  5

The elements of 'first' in inorder:
        -11 8 -3 12 -1 -9 -5 2 16 10 6 -13 4 14 -7
The elements of 'first' in preorder:
        2 -1 -3 8 -11 12 -5 -9 4 6 10 16 -13 -7 14
The elements of 'first' in postorder:
        -11 8 12 -3 -9 -5 -1 16 10 -13 6 14 -7 4 2

second: tree is not empty
        no of nodes    =  9
        height of tree =  4

The elements of 'second' in inorder:
        7 3.25 0.75 -7.75 -0.5 -11.5 4.5 -4 8.25
The elements of 'second' in preorder:
        -0.5 0.75 3.25 7 -7.75 -4 4.5 -11.5 8.25
The elements of 'second' in postorder:
        7 3.25 -7.75 0.75 -11.5 4.5 8.25 -4 -0.5

third: tree is not empty
        no of nodes    =  7
        height of tree =  4

The elements of 'third' in inorder:
        objects. list is string This of a
The elements of 'third' in preorder:
        This is list objects. string a of
The elements of 'third' in postorder:
        objects. list string is of a This
</code></pre>

<p>My Results:</p>

<pre><code>first: tree is not empty
       no of nodes    = 15
       height of tree = 4
The elements of 'first' in inorder:
-9 -5 4 16 -1 -13 10 -7 2 14 8 6 -3 -11 12
The elements of 'first' in preorder:
2 -1 4 -5 -9 16 -7 10 -13 -3 6 8 14 12 -11
The elements of 'first' in postorder:
-9 -5 16 4 -13 10 -7 -1 14 8 6 -11 12 -3 2
second: tree is not empty
       no of nodes    = 9
       height of tree = 3
The elements of 'second' in inorder:
-7.75 -4 0.75 -11.5 8.25 -0.5 7 4.5 3.25
The elements of 'second' in preorder:
-0.5 0.75 -4 -7.75 8.25 -11.5 3.25 4.5 7
The elements of 'second' in postorder:
-7.75 -4 -11.5 8.25 0.75 7 4.5 3.25 -0.5
third: tree is not empty
       no of nodes    = 7
       height of tree = 3
The elements of 'third' in inorder:
string a is This objects. of list
The elements of 'third' in preorder:
This is a string list of objects.
The elements of 'third' in postorder:
string a is objects. of list This
</code></pre>

<p>Code: </p>

<pre><code>template &lt;class T&gt;
void binTree&lt;T&gt;::insert(binTreeNode &lt; T &gt;*&amp; node, const T&amp; data) {
        if(node == NULL) {
                root = new binTreeNode&lt;T&gt;(data, NULL, NULL);
                return;
        }

        binTreeNode&lt;T&gt;* ptr1 = node;
        binTreeNode&lt;T&gt;* ptr2 = node;
        bool placeRight = 0;
        while(ptr1 != NULL) {
                ptr2 = ptr1;
                if(height(ptr1-&gt;left) &gt; height(ptr1-&gt;right)) {
                        placeRight = true;
                        ptr1 = ptr1-&gt;right;
                } else if (height(ptr1-&gt;right) &gt; height(ptr1-&gt;left)) {
                        placeRight = false;
                        ptr1 = ptr1-&gt;left;
                } else {
                        placeRight = false;
                        ptr1 = ptr1-&gt;left;
                }
        }

        if(placeRight) {
                ptr2-&gt;right = new binTreeNode&lt;T&gt;(data, NULL, NULL);
        } else {
                ptr2-&gt;left = new binTreeNode&lt;T&gt;(data, NULL, NULL);
        }
}
</code></pre>

<p>Driver Program:</p>

<pre><code>const vector&lt;int&gt; A { 1, -2, 3, -4, 5, -6, 7, -8, 9, -10, 11, -12, 13, -14, 15 };
const vector&lt;float&gt; B { 0.5, 1.75, -3, 4.25, 5.50, -6.75, 8, 9.25, -10.5 };
const vector&lt;string&gt; C { "This", "is", "a", "list", "of", "string", "objects." };
int main() {
        binTree&lt;int&gt; intTree = binTree&lt;int&gt;();
        binTree&lt;float&gt; floatTree = binTree&lt;float&gt;();
        binTree&lt;string&gt; strTree = binTree&lt;string&gt;();

        for (std::vector&lt;int&gt;::const_iterator it = A.begin() ; it != A.end(); ++it) {
                intTree.insert(*it);
        }
        intTree.preorder(increase);
        cout &lt;&lt; "first: ";
        header(intTree);

        inorder(intTree, "first");
        preorder(intTree, "first");
        postOrder(intTree, "first");
}
</code></pre>

<p>Functions to display results: (should be correct)</p>

<pre><code>template &lt;class T&gt;
void binTree&lt;T&gt;::inorder(binTreeNode &lt; T &gt;* node, void (*f)(T&amp;))
{
        if (node == NULL) {
                return;
        }
        inorder(node-&gt;left,f);
        f(node-&gt;data);
        inorder(node-&gt;right,f);
}


template &lt;class T&gt;
void binTree&lt;T&gt;::preorder(binTreeNode &lt; T &gt;* node, void(*f)(T&amp;))
{
        if (node == NULL) {
                return;
        }
        f(node-&gt;data);
        preorder(node-&gt;left, f);
        preorder(node-&gt;right, f);
}


template &lt;class T&gt;
void binTree&lt;T&gt;::postorder(binTreeNode &lt; T &gt;* node, void(*f)(T&amp;))
{
        if (node == NULL) {
                return;
        }
        postorder(node-&gt;left, f);
        postorder(node-&gt;right, f);
        f(node-&gt;data);
}

template &lt;class T&gt;
    int binTree&lt;T&gt;::height(binTreeNode &lt;T&gt;* node) const {
    if (node == NULL || ((node-&gt;left == NULL) &amp;&amp; (node-&gt;right == NULL))) {
            return 0;
    }

    int leftSide = height(node-&gt;left);
    int rightSide = height(node-&gt;right);

    if (leftSide &gt; rightSide) {
            return leftSide + 1;
    } else {
            return rightSide + 1;
    }
}
</code></pre>
