Binary tree in C

bintree.c

#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;
}

void print(struct node* n)
{
    if ((n == NULL) || (n->left == NULL && n->right == NULL))
    {
        return;
    }

    if (n->left != NULL)
    {
        printf("%d ", n->left->data);
    }

    printf("%d ", n->data);

    if (n->right != NULL)
    {
        printf("%d ", n->right->data);
    }
    printf("\n");

    print(n->right);
}

int main()
{
/*
            NULL                        1                          0
             ^                          ^                         / \
                         --->                        --->        1   2
                                                                     ^

 +-----------------------+  +-----------------------+  +-----------------------+
 |                       |  |                       |  |           |           |
 |                       |  |                       |  |           |           |
 |                       |  |                       |  |           |           |
 |          NULL         |  |           1           |  |     1     |     2     |
 |                       |  |                       |  |           |           |
 |                       |  |                       |  |           |           |
 |                       |  |                       |  |           |           |
 +-----------------------+  +-----------------------+  +-----------------------+
             A                          B                          C
*/
    // A
    struct node* root = NULL;

    // B
    root = create_node(1);
    printf("B\n");
    print(root);

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

    // C
    insert(root, create_node(2));
    printf("C\n");
    print(root);

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

/*
             0                          0                          0
            / \                        / \                        / \
           1   0         --->         1   0         --->         1   0
              / \                        / \                        / \
             2   3                      4   0                      5   0
             ^                          ^  / \                     ^  / \
                                          3   2                      3   0
                                                                        / \
                                                                       2   4

 +-----------------------+  +-----------------------+  +-----------------------+
 |           |           |  |           |           |  |           |           |
 |           |     2     |  |           |     4     |  |           |     5     |
 |           |     ^     |  |           |     ^     |  |           |     ^     |
 |     1     |-----------|  |     1     |-----------|  |     1     |-----------|
 |           |           |  |           |     |     |  |           |  2  |     |
 |           |     3     |  |           |  2  |  3  |  |           |-----|  3  |
 |           |           |  |           |     |     |  |           |  4  |     |
 +-----------------------+  +-----------------------+  +-----------------------+
             X                         Y                          Z
*/
    // X
    insert(root->right, create_node(3));
    printf("X\n");
    print(root);

    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));
    printf("Y\n");
    print(root);

    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));
    printf("Z\n");
    print(root);

    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;
}