How to insert a linked list at node of binary search tree?

Question

I would like to populate a linked list which is in a node of a binary search tree. If the user already exits in the list add the ip to the linked list for that specific user.

This is what I have tried so far:

My Data Structures:

typedef struct ip{
    int ip;
    struct ip *ipNext;
}IP;

typedef struct bstNode
{
    char data[32];
    struct bstNode* left;
    struct bstNode* right;
    IP *ipHead; //Pointer to linked list. 
}bstNode;

This is where I am having issues

My insert function to insert the IP address into the list for user:

bstNode insertIP(bstNode *head, char *username, int ip){

 if (search(username)==1)
    {
        if (head->ipHead == NULL)
    {
        IP *temp; 
        temp = (IP*)malloc(sizeof(IP));
        temp->ip = ip;
        temp->ipNext = NULL;
    }else{
        head->ipHead->ip= ip;
        head->ipHead->ipNext=NULL;
    }
}

Insert Function (This works):

bstNode *insert(bstNode *node, char *word)
{
    if(node==NULL){
        node= malloc(sizeof(bstNode));
        //IP* ipNode=malloc(sizeof(IP));
        strcpy(node->data, word);
        node->left=NULL;
        node->right=NULL;
    }
    else{
        if(strcmp(word, node->data)<0)
            node->left=insert(node->left, word);
        else if(strcmp(word, node->data)>0)
            node->right=insert(node->right, word);
    }
    return node;
}

Search Function (This works):

void search(char* user, bstNode* root)  
{
    int res;
    if( root!= NULL ) {
        res = strcmp(root, root->data);
        if( res < 0)
            search( user, root->left);
        else if( res > 0)
            search( user, root->right);
        else
            printf("User Found\n");   
            return 1;                       
    }
    else printf("\nNot in tree\n");
    return 0;
}

In your `insertIP` function, if you hit `else` you will need to iterate over your list until `->ipNext=NULL` and then allocate insert `tmp` at that address and set the value to `ip`. Since you will always allocate `if (search(username)==1)` the allocation of `temp` should be before the `if (head->ipHead == NULL)`. And... There is no need to cast the return of `malloc`, it is unnecessary. See: [**Do I cast the result of malloc?**](http://stackoverflow.com/q/605845/995714) — David C. Rankin, Mar 21 '18 at 06:47

Akash · Answer 1 · 2018-03-21T08:04:08.227

When you find that user already exist in the tree, then first you have to store that bstNode which contains the given user. After that you would have to traverse the linked list of that bstNode to append the ip at the last. There is one more problem with you code in case where the linked link is NULL. You would have to assign the new node address to the ipHead. Currently you have creating a temp node and not assigning that to head.

score 0 · Answer 2 · answered Mar 21 '18 at 07:10

1st issue: when you create temp you dont assign it to the head->ipHead.

2nd issue: when ipHead exists you still have te allocate memory for the new list node and have to iterate over the whole list if you want to add it at the end. You can also add it at the begining of the list.

3rd issue: the searching function should return the node in the tree if it found the username. I guess that you dont want to always add new list nodes tho the first tree node. I suggest that you traverse the tree using local variable in function - not recursion.

Urovoros Ofis · Answer 3 · 2020-10-07T11:59:48.507

Recently I coded a binary search tree in which each tree node hosts a linked list (list nodes are singly linked) and I used the following data structure (if someone needs the whole code, let me know).

// data in each
// list node
struct data_info
{
    //body of data
};

typedef struct data_info Item;

// list node
typedef struct lnode
{
    Item data_item;
    struct lnode * next;
} Lnode;

// List points to
// first list node
typedef Lnode * List;

// tree node contains
// linked list
typedef struct trnode
{
    List list_item;
    struct trnode * left;   // pointer to right branch
    struct trnode * right;  // pointer to left branch
} Trnode;

// tree of linked lists
typedef struct tree
{
    Trnode * root;          // pointer to root of tree
    int size;               // number of list nodes in tree
} Tree;

How to insert a linked list at node of binary search tree?

3 Answers3