Inserting into a binary expression tree with GOTO

Question

I'm working on a binary space partition tree.

For the time being, the nodes are only inserted into the right. A node that has children will have 0 as data. Here are the insertion rules.

If the insertion node has data and no parent, the current data becames the left child, and the node to insert goes to the right.

1       0
^ ---> / \
      1   2

If the node has a parent, is a the left child of the parent and has data, the node is reinserted in the parent's right node, and the inserted node takes its place

  0          0
 / \        / \ 
1   2 ---> 3   0
^             / \
             2   1

I'd like to have a feedback on my insert function. I put a goto statement to not repeat code, but I'd like to avoid it to make the function more clear.

Live on Coliru with verbose output

#include <assert.h>
#include <stdlib.h>
#include <stdio.h>

struct node
{
    int data;

    struct node* parent;
    struct node* left;
    struct node* right;
};

struct node* create_node(int i)
{
    struct node* n = calloc(1, sizeof(struct node));

    n->data = i;

    n->parent = NULL;
    n->left = NULL;
    n->right = NULL;

    return n;
}

void destroy_node(struct node* n)
{
    if (n->left != NULL)
    {
        destroy_node(n->left);
    }

    if (n->right != NULL)
    {
        destroy_node(n->right);
    }

    free(n);
}

void insert(struct node* i, struct node* n)
{
    printf("insert at %d node %d\n", i->data, n->data);
    // TODO : insert rightmost or leftmost
    if (i->parent != NULL)
    {
        if (i->parent->left == i)
        {
            // if insert node is left
            struct node* p = i->parent;
            i->parent = NULL;
            insert(p->right, i);
            p->left = n;
            n->parent = p;
            return;
        }
        else if (i->parent->right == i)
        {
            // if insert node is right
            if ((i->left == NULL) && (i->right == NULL))
            {
                // if insert node is rightmost
                goto insert;
            }

            if (i->right != NULL)
            {
                // if right node is not rightmost
                insert(i->right, n);
                return;
            }
        }
    }
    else if (i->parent == NULL)
    {
        // if insert node is root
        if ((i->left == NULL) && (i->right == NULL))
        {
            // if insert node has no children
            goto insert;
        }
        else if (i->right != NULL)
        {
            // if right child is not null
            insert(i->right, n);
            return;
        }
    }

insert: ;
    int value = i->data;
    i->data = 0;

    struct node* left = create_node(value);
    left->parent = i;

    n->parent = i;

    i->left = left;
    i->right = n;

    return;
}

int main()
{
    // A
    struct node* root = NULL;

    // B
    root = create_node(1);

    assert(root->data == 1);
    assert(root->left == NULL);
    assert(root->right == NULL);

    // C
    insert(root, create_node(2));

    assert(root->data == 0);
    assert(root->left->data == 1);
    assert(root->right->data == 2);

    // X
    insert(root->right, create_node(3));

    assert(root->right->data == 0);
    assert(root->right->left->data == 2);
    assert(root->right->right->data == 3);

    // Y
    insert(root->right->left, create_node(4));

    assert(root->right->left->data == 4);
    assert(root->right->right->data == 0);
    assert(root->right->right->left->data == 3);
    assert(root->right->right->right->data == 2);

    // Z
    insert(root->right->left, create_node(5));

    assert(root->right->left->data == 5);
    assert(root->right->right->left->data == 3);
    assert(root->right->right->right->left->data == 2);
    assert(root->right->right->right->right->data == 4);

    destroy_node(root);

    return 0;
}

Answer 1

Your insertion requirements are mighty strange, but I guess you have some reason for them, so I won't comment further on that.

• One of the huge benefits of having a parent pointer in each node is that you can get rid of recursion entirely. In your case, getting rid of recursion will improve performance and stack consumption significantly. Since your recursion is not tail recursion, there is no sensible way the compiler can optimize it - so the result will be very inefficient code. Recursion should be avoided in general, since it slow, memory intense, dangerous and sometimes hard to read.

  Instead of using recursion, you can simply loop down the list of nodes until you hit NULL in a leaf, checking if each node sates the insert condition along the way. Keep track of the current node by pointing at it with a local pointer, rather than a pointer passed as parameter to a recursive function.

  If you need to step up in the tree, you do it by setting the current pointer to its parent, which is then equivalent of returning from a recursive function.

• Your goto and multiple returns is a bit hard to read and follow. By getting rid of the recursion, you'll get rid of all of these too. Your new function should look something like this pseudo:

  insert function
    if we are at root
      special case, handle it
    else
      loop looking for candidate to insert
      if candidate found, set pointer to it and break loop
  
    if candidate found
      create node
      insert node at candidate
  

• Similarly, your destroy_node function could be rewritten with a loop instead of recursion, although performance is less of an issue here.

• The create_node function is mostly pointless, it is just a call to malloc/calloc and not much else of value. You set all the node's pointers manually anyway, so setting them to NULL in advance adds nothing. You might as well skip this function and just call malloc. (Also, the mandatory remark: you should check if malloc returns NULL and add some error handling.)

• It is a bad idea to pick the same identifier for the function, as for the labels inside it. Yes they reside in different namespaces, but that's no excuse for using the same name. Always use distinctive names for every single identifier in your program, no matter if it is a function, variable, label, macro etc.

• Having an empty return ; at the end of a void function fills no purpose.

• The printf should naturally not be part of the insert algorithm, but I take it that's just debug code that will be removed later(?).

• Minor remark: since you initialize all members of the struct, there is no reason to use calloc. malloc will be slightly faster.

• int main() is obsolete style in C. You should use int main (void) (or alternatively argc/argv). Not to be confused with C++, where int main() is fine and means the same thing as int main (void).