Delete node from BST in 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) ? (same for the two lines of code right after)

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 1

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;