Is it necessary to reassign 'root' node on reading the first value in a Binary Search Tree?

Question

I was working on trying to implement Binary Search Tree in C and had come across this issue. I have made my Insert function of void type and hence I do not have a variable which assigns the value of this call-back. When I run the program I do not see any output. Is this something to do with me not assigning my root node pointer once it has changed from NULL to pointing to a value?

#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
   int data;
   struct node *left, *right;
}Node;

void addToNode(Node *A, int value)
{
   A->data=value;
   A->left=NULL;
   A->right=NULL;
}

void insert(Node *A, int value)
{
   if(A==NULL)
   {
      A = (Node*)malloc(sizeof(Node));
      addToNode(A, value);
      // printf("Hello\n");
      return;
   }
   else
   {
      if(value>A->data)
      {
         insert(A->right, value);
         // printf("Hello\n");
         return;
      }
      else if(value<A->data)
      {
         insert(A->right, value);
         // printf("Hello\n");
         return;
      }
  }
}

void inorder(Node *root)
{
   if (root != NULL)
   {
      // printf("Hello\n");
      inorder(root->left);
      printf("%d \n", root->data);
      inorder(root->right);
   }
}

int main()
{
    Node *root = NULL;
    int A[]={45,32,56,23,11,89};
    for(int i=0; i<6; i++) insert(root,A[i]);
    inorder(root);
}

Sergey Kalinichenko · Answer 1 · 2018-05-22T10:00:52.873

0

The problem is not that your function is void, but that it takes the root pointer by value, rather than by pointer. That is why this assignment

A = (Node*)malloc(sizeof(Node));

remains local to your insert function; variable root of the main remains unassigned.

Modify your function to take the node by pointer:

void insert(Node **A, int value) {
    if(*A == NULL) {
        *A = malloc(sizeof(Node));
        addToNode(*A, value);
        return;
    }
    Node *root = *A;
    if (value > root->data) {
        insert(&root->right, value);
    } else if (value < root->data) {
        insert(&root->left, value);
    }
}

Now the call in the main would look like insert(&root, A[i]);, so the assignment *A = malloc(sizeof(Node)) would modify root as necessary.

edited May 22 '18 at 10:00

answered May 22 '18 at 09:45

Sergey Kalinichenko

714,442
84
1,110
1,523

So what I had done previously was Pass by Value, this is Pass by Reference which does change the value at that particular pointer? – Aditya Vinod Kumar May 22 '18 at 19:28
@AdityaVinodKumar C does not have a pass-by-reference. You model it by passing a pointer, with the pointer itself being passed by value. This is exactly how this solution works - it passes a pointer (which happens to be a pointer to a pointer, because we want to modify a pointer) and uses `*` to dereference the pointer. – Sergey Kalinichenko May 22 '18 at 19:31

score 0 · Answer 2 · answered May 22 '18 at 09:46

You should pass Node as pointer to pointer. Because you want to make alteration on the pointer itself.

void insert(Node **A, int value)
{
    if(*A==NULL)
    {
        *A = (Node*)malloc(sizeof(Node));
        addToNode(*A, value);
        // printf("Hello\n");
        return;
    }
    else
    {
        if(value>(*A)->data)
        {
            insert(&(*A)->right, value);
            // printf("Hello\n");
            return;
        }
        else if(value<(*A)->data)
        {
            insert(&(*A)->left, value);
            // printf("Hello\n");
            return;
        }
    }
}

Is it necessary to reassign 'root' node on reading the first value in a Binary Search Tree?

2 Answers2