Giorgio M. - 1 year ago 79

C Question

i was trying to understand this function founded online for deleting a node from a BST. There are some things i can't understand

This is the code :

`struct Node* Delete(struct Node *root, int data) {`

if (root == NULL) {

return NULL;

}

if (data > root->data) { // data is in the left sub tree.

root->left = Delete(root->left, data);

} else if (data > root->data) { // data is in the right sub tree.

root->right = Delete(root->right, data);

} else {

// case 1: no children

if (root->left == NULL && root->right == NULL) {

delete(root); // wipe out the memory, in C, use free function

root = NULL;

}

// case 2: one child (right)

else if (root->left == NULL) {

struct Node *temp = root; // save current node as a backup

root = root->right;

delete temp;

}

// case 3: one child (left)

else if (root->right == NULL) {

struct Node *temp = root; // save current node as a backup

root = root->left;

delete temp;

}

// case 4: two children

else {

struct Node *temp = FindMin(root->right); // find minimal value of right sub tree

root->data = temp->data; // duplicate the node

root->right = Delete(root->right, temp->data); // delete the duplicate node

}

}

return root; // parent node can update reference

}

Questions :

1) Why it is

`if (data > root->data) { // data is in the left sub tree.`

root->left = Delete(root->left, data);

shouldn't it be

`if(data < root->data)`

2) the function return a pointer to node,does that mean that in the main function i have to do something like this?

`int main(){`

struct Node *tree=malloc(sizeof(Node));

...

struct Node *new_tree=malloc(sizeof(Node));

new_tree= Delete(tree,24);

So the function replace the old tree with a new tree without the node with the val 24?if i want the function to be of type void should i use double pointers?

Answer Source

For your first question you have right it should be: `if(data < root->data)`

.
For the second question not exactly. You obviously should define a pointer head which is the head of the tree and create an function which inserts data to bst, so this function does the malloc. All you nead in your main is the head pointer initialized to NULL in the beginning so it should look like:

```
int main(){
struct Node *tree=NULL;
int number=...;
...
input_to_bst(&tree,number);
...
new_tree= Delete(tree,24);
```

Also note that new tree doesn't need to have malloc since your function returns a pointer that already shows to a struct and what you do is that new_tree will also point this struct.

For your final question yes of course you could pass double pointer (in fact I followed this way in the definition of `input_to_bst(&tree);`

).

An example of function input_to_bst definition could be:

```
void input_to_bst(treeptr* head,int number){
if((*head)==NULL){
(*head)=(treeptr)malloc(sizeof(struct tree));
(*head)->data=number;
(*head)->left=NULL;
(*head)->right=NULL;
}
else{
if(((*head)->data)>number) input_to_bst(&((*head)->left),number);
else (((*head)->data)<number) input_to_bst(&((*head)->right),number);
}
}
```

where we suppose that we have defined the structs:

```
struct tree{
int data;
struct tree* right;
struct tree* left;
};
typedef struct tree* treeptr;
```