using recursive function to insert item in Binary search tree

Question

Issue : How to insert item in BST when pointer is in nested structure?
Language : C only.

I know about binary search tree and how to do insert delete and print. But this time I have nested structure and inner structure contains pointers. SO I need help /hint how to do that.

Example traditionally we have structure like this

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

And to insert node at appropriate place it is something like this

struct node* insert(struct node* node, int data)
 {
     if (node == NULL) 
    {
       // code to implement root code;
       node = create_node(); 
     }
     else
     {
       // 2. Otherwise, recur down the tree
       if (data <= node->data) 
       { 
         node->left = insert(node->left, data);
       } 
       else 
      {
        node->right = insert(node->right, data);
      }
     return(node);
     }
 }

But what I have now is nested structure

struct link
{
   struct link *left;
   struct link *right;
};

struct item
{
   struct link link; 
   uint8_t c;
};

Since here item does not have pointer to left and right , how would I insert item in recursive fashion. my attempt

 struct item* insert_item( item* root, uint8_t key )
{
    if( !root )
    {
        root = create_item( key ); // some function create_item to create first item
    }
    /* Otherwise, recur down the tree */
    else
   {
        if( key < root->c )
        {
            insert_item( ); // The node  does not have pointer ?? how would I traverse left or right?
        }
        else
        {
          // how would I apply recursive to right side of tree?

        }
   }
  return root;
}

Answer 1

The solution is to use casts.

int insert(struct link** node, uint8_t data) {
  if (*node == NULL) {
    // code to implement root code;
    *node = malloc( sizeof(struct item) );
    if(*node == NULL) return -1;
    ( (struct item*) *node)->c = data;
    ( (struct item*) *node)->link.left = ( (struct item*) *node)->link.right = NULL;
  } else {
    // 2. Otherwise, recur down the tree
    int rc;
    if (data <= ( (struct item*) *node)->c) { 
      rc = insert(&( ( (struct item*) *node)->link.left ), data);
      if( rc < 0 ) return rc;
    } else {
      rc = insert(&( ( (struct item*) *node)->link.right ), data);
      if( rc < 0 ) return rc;
    }
  }
  return 0;
}

Note that I made a few changes to your code. Namely, I no longer assume that node->left and node->right are not assigned.

Answer 2

In insert_item() use something like this to traverse left or right:

root.link->left
root.link->right

But remember, in your insert method you are returning void except *node like traditional insertion.

Note, Your struct node* insert(struct node* node, int data) will give Undefined Behavior because of no return statement when node == NULL.

EDIT: As OP asked in the comment, "but root.link->left is of type link. how it will work ?"

So change

struct link
{
   struct link *left;
   struct link *right;
};

to,

struct link
{
   struct item *left;
   struct item *right;
};

That will solve your problem. But don't forget the forward declaration of struct item. Otherwise in struct link compiler will raise error as it don't know what item is.