insert_modified.cpp

tree_node* insert(tree_node* n, int value)
{
    if (n == NULL)
    {
        return NULL;
    }
    
    tree_node* x_parent = NULL;
    tree_node* x = n;

    while (x != NULL)
    {
        if (value == x->data)
        {
            return x;
        }
        
        x_parent = x;   // Keep track of the last node we have visited.

        if (value < x->data)
        {
            x = x->left;
        }
        else
        {
            x = x->right;
        }
    }
    
    //
    // x now points to NULL and x_parent points to the last node visited
    // We compare value with the value stored at the node to which
    // x_parent points in order to know whether we should insert value
    // at x_parent->left or x_parent->right.
    //
    if (value < x_parent->data)
    {
        x_parent->left = new tree_node();
        x_parent->left->data = value;
        x_parent->left->left = x_parent->left->right = NULL;
        return x_parent->left;
    }
    
    // else use x_parent->right
    x_parent->right = new tree_node();
    x_parent->right->data = value;
    x_parent->right->left = x_parent->right->right = NULL;
    return x_parent->right;
}