2
\$\begingroup\$

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?

\$\endgroup\$
1
  • \$\begingroup\$ Your version of code looks a bit complicated. \$\endgroup\$ Oct 22, 2016 at 18:14

2 Answers 2

2
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ A small change of API for a very elegant solution! The only drawback is the lack of error checking. In case create_node() fails, the whole tree will be likely lost if the function is called carelessly as: root = add_internal(root, value); \$\endgroup\$
    – chqrlie
    Oct 29, 2016 at 18:24
0
\$\begingroup\$

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);
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.