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

return(node); wrong position.

BLUEPIXY
– BLUEPIXY

2015-06-17 10:19:52 +00:00
Commented Jun 17, 2015 at 10:19 — BLUEPIXY
– BLUEPIXY, Commented Jun 17, 2015 at 10:19

ceilingcat · Accepted Answer · 2016-10-22 00:48:46Z

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.

answered Oct 22, 2016 at 0:48

ceilingcat

8018 silver badges13 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

mazhar islam · Accepted Answer · 2015-06-17 12:45:57Z

1

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.

edited Jun 17, 2015 at 12:45

answered Jun 17, 2015 at 10:15

mazhar islam

5,6293 gold badges23 silver badges42 bronze badges

6 Comments

samprat Over a year ago

Thanks for the answer . But I have one doubt. insert_item takes item* as its paramater but root.link->left is of type link. how it will work ?

mazhar islam Over a year ago

@samprat, sorry for the late reply as I was busy, see the edited answer.

samprat Over a year ago

I cannot able to change structure. So do you think there is any other way?

mazhar islam Over a year ago

According to your structure, items knows link whereas link knows only links. Then how can you point a new item from link? Then is it possible to contract a tree?

samprat Over a year ago

rakeb , I guess that is the trick? I need to find solution using above structure

|

Collectives™ on Stack Overflow

using recursive function to insert item in Binary search tree

2 Answers 2

Comments

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related