How to make a recursive insert for a binary tree more effective (efficient)?
<p>This code is modified from a Stanford resource located <a href="http://cslibrary.stanford.edu/110/BinaryTrees.html" rel="nofollow">here</a>.</p>

<p>I started with this after some modifying to C++ conventions:</p>

<pre><code>#include &lt;iostream&gt;
#include &lt;string&gt;

using namespace std;

template &lt; typename A, typename B &gt; class binary_tree
{
    public:

    class node 
    {
            public:
            A key;
        B value;
            node* left;
            node* right;
    };

    typedef node* nodePointer;

    nodePointer HP;

    nodePointer newNode( A key, B value ) 
    {
            nodePointer NP = new( node );
            NP-&gt;key = key;
                NP-&gt;value = value;
            NP-&gt;left = NULL;
            NP-&gt;right = NULL;
                return NP;
    }

    void insert( A key, B value )
    {
        insertI( this-&gt;HP, key, value );
    }

    nodePointer insertI( nodePointer NP, A key, B value ) 
    {
        if ( NP == NULL ) 
        {
            return newNode( key, value );
        }
        else 
        {
            if (key &lt; NP-&gt;key) 
            {
                NP-&gt;left = insertI( NP-&gt;left, key, value );
            }
            else 
            {      
                NP-&gt;right = insertI( NP-&gt;right, key, value );
            }
            return NP;
        }
    }

    binary_tree(A key, B value)
    { 
        this-&gt;HP = insertI(NULL, key, value );
    }
};
</code></pre>

<p>To eliminate passing by value the key/value pair for each activation frame I updated the insertI() parameters to pass by const reference like this:</p>

<pre><code>nodePointer insertI( nodePointer NP, const A&amp; key, const B&amp; value ) 
{
    if ( NP == NULL ) 
    {
        return newNode( key, value );
    }
    else 
    {
        if (key &lt; NP-&gt;key) 
        {
            NP-&gt;left = insert( NP-&gt;left, key, value );
        }
        else 
        {      
            NP-&gt;right = insert( NP-&gt;right, key, value );
        }
        return NP;
    }
}
</code></pre>

<p>Right now I can only define the function inline b.c. I'm using an online compiler.  But what is faster - inline, or defined outside of the class?</p>

<p>Also, this is just a stub, obviously the class over all needs more work.  This question just regards the insertI() function.</p>

<p>Is there anything else I can do to make the insert more efficient?</p>

<p><strong>Links</strong></p>

<p>(http://en.wikipedia.org/wiki/Binary_search_tree#Searching)</p>

<p>(http://en.wikipedia.org/wiki/Binary_search_algorithm)</p>

<p><a href="http://stackoverflow.com/questions/207496/c-binary-search-tree-insert-via-recursion">Another Approach</a></p>

<p><a href="http://en.wikipedia.org/wiki/Tail_call" rel="nofollow">Tail Recursion</a></p>

<p><strong>Notes</strong></p>

<blockquote>
  <p>This operation requires O(log n) time in the average case, but needs
  O(n) time in the worst case, when the unbalanced tree resembles a
  linked list (degenerate tree).</p>
</blockquote>

<p><strong>Related</strong></p>
