newnode.c

 struct node_s * add_node(struct node_s ** tree, struct node_s * leaf)
{
        if(*tree == NULL)
                *tree = leaf;
        else if((*tree)->key > leaf->key) {
                leaf->right = *tree;
                *tree = leaf;
        }
        else if((*tree)->key < leaf->key) {
                leaf->left = *tree;
                *tree = leaf;
        }
        else {  // ==
                free(*tree);
                *tree = leaf;
        }
        return leaf;
}