How to insert a node in a BST without using CC

So I have a piece of code, where I have to add a node to a BST. My struct is the following:

typedef struct _CC_TREE {
    // Members
    int Value;
    struct _CC_TREE* LChild;
    struct _CC_TREE* RChild;
} CC_TREE;

The insert function in the header file looks like this:

int TreeInsert(CC_TREE *Tree, int Value);

where I have to return the status of the insert.

I tried doing it with another function and add it to the Tree

CC_TREE* InsertNewNode(CC_TREE* Tree, int Value)
{
    if (NULL == Tree)
    {
        Tree = (CC_TREE*)malloc(sizeof(CC_TREE));
        Tree->LChild = NULL;
        Tree->RChild = NULL;
        Tree->Value = Value;
        return Tree;
    }
    if (Value <= Tree->Value)
    {
        Tree->LChild = InsertNewNode(Tree->LChild, Value);
    }
    else if (Value >= Tree->Value)
    {
        Tree->RChild = InsertNewNode(Tree->RChild, Value);
    }
    return Tree;
}

int TreeInsert(CC_TREE *Tree, int Value)
{
    CC_UNREFERENCED_PARAMETER(Tree);
    CC_UNREFERENCED_PARAMETER(Value);

    Tree = InsertNewNode(Tree, Value);
    return 0;
}

I try and construct the tree in my main function:

int retVal = -1;
CC_TREE* usedTree = NULL;

retVal = TreeCreate(&usedTree);
if (0 != retVal)
{
    printf("TreeCreate failed!\n");
    goto cleanup;
}

retVal = TreeInsert(usedTree, 20);
if (0 != retVal)
{
    printf("TreeInsert failed!\n");
}

but for some reason the usedTree remains null. I know that I should use CC_TREE** Tree in the insert function, but I am not allowed to.

CodePudding user response：

The insert function in the header file looks like this:
int TreeInsert(CC_TREE *Tree, int Value);

If you cannot change the function signature or (ew!) use a global variable to return the root pointer to the caller, then your best alternative is probably to use a dummy tree root. That would look something like this:

int TreeInsert(CC_TREE *Tree, int Value) {
    // Tree points to a dummy root node containing no data.
    // Tree->LChild is the actual root pointer
    CC_TREE *root = Tree->LChild;
    int status = 0;

    // ... perform insertion, possibly resulting in a different value for the
    // root pointer ...

    Tree->LChild = root;
    return status;
}

That assumes that the first argument to TreeInsert() is always a valid pointer to a CC_TREE. If you do this, then all other tree functions should work analogously.

You would use that from main() like so:

    int retVal;
    CC_TREE dummy_tree_root = { 0 };
    
    retVal = TreeInsert(&dummy_tree_root, 42);

Note that this approach in effect uses a double pointer via an indirect route (no pun intended). A CC_TREE * is not itself a double pointer, but there are still two levels of indirection between that pointer and either the left or the right child of the node to which it points.

Note also that a cleaner way of doing this would involve providing a wrapper structure representing the overall tree instead of using a bare tree node or tree node pointer for the purpose. The data structures would be something like this:

struct node {
    int value;
    struct node *left;
    struct node *right;
};

struct tree {
    struct node *root;
    // optionally other data, such as size, height, etc.
};