Inserting into a binary search tree in C

Question

I am in the process of refactoring this simple binary search tree code responsible for adding new values:

void add_internal(Node *root, int value) {
    // Decide whether to insert left or right
    if (root->value >= value) {
        // Decide whether to insert here or down the subtree
        if (root->left) {
            add_internal(root->left, value);
        } else {
            root->left = create_node(value);
        }
    } else {
        // Decide whether to insert here or down the subtree
        if (root->right) {
            add_internal(root->right, value);
        } else {
            root->right = create_node(value);
        }
    }
}

to this:

Node **relevant_node = (root->value >= value) ? &root->left : &root->right;

if (*relevant_node) {
    add_internal(*relevant_node, value);
} else {
    *relevant_node = create_node(value);
}

Both solutions work. My refactored one tho is pretty much the result of trial and error, will it be as robust as the first solution?

Answer 1

There is a third option:

Node *add_internal(Node *root, int value) {
    if(root == NULL) {
        return create_node(value);
    }

    // Decide whether to insert left or right
    if (root->value >= value) {
        root->left = add_internal(root->left, value);
    } else {
        root->right = add_internal(root->right, value);
    }
    return root;
}

Basically moves the null test into the recursive call.

However this version requires it to be called as root = add_internal(root, value);. But it has the advantage that it can deal with a null root in a transparent way.

Answer 2

Here is an alternative to ratchet freak's elegant solution that better handles node creation errors:

Node *add_internal(Node **rootp, int value) {
    Node *root = *rootp;
    if (root == NULL) {
        return *rootp = create_node(value);
    } else
    if (root->value >= value) {
        return add_internal(&root->left, value);
    } else {
        return add_internal(&root->right, value);
    }
}

This API can be called this way:

Node *root = NULL;
...
Node *node = add_internal(&root, value);
if (node == NULL) {
    // handle node insertion error
}

Also note that this function uses tail recursion, which may be compiled as a simple loop by modern translator. Nevertheless, here is a non recursive version:

Node *add_internal(Node **rootp, int value) {
    while (*rootp) {
        rootp = (*rootp)->value >= value ? &root->left : &root->right;
    }
    return *rootp = create_node(value);
}