Home > Blockchain >  Binary search tree algorithm crashing when passing a parameter that isn't in the tree to the se
Binary search tree algorithm crashing when passing a parameter that isn't in the tree to the se

Time:10-05

i tried building a binary search tree, everything worked fine when i gave it parameters that were in in the tree, but i wanted to see if it would print 0 when it couldn't find the int in the tree instead when i call search it's crashing.

i tried adding a condition after the first if statement but that ruined the recursion here's the code:

   struct node
{
  int data;
  node* left;
  node* right;
  
  node(int d)
  {
    data = d; 
    left = right = NULL;

  }

};

node* insert(node *root, int n)
{
  if(root == NULL)
  {
    return new node(n);
  }
  else
  {
    node* y;

    if(n <= root->data)
    {
      y = insert(root->left, n);
      root->left = y;
    }
    else
    {
      y = insert(root->right, n);
      root->right = y;
    }

    return root;
  }

}

node* search(node *root,int n)
{
  if(root == NULL || root->data == n)
  {
    return root;
  }
  
  if(root->data < n)
  {
    return search(root->right, n);
  }
  return search(root->left, n);
}

int treemax(node *root)
{
   while(root->right != NULL)
   {
     root = root->right;
   }
   return root->data;
}

int treemin(node *root)
{
  while(root->left != NULL)
  {
    root = root->left;
  }
  return root->data;
}

int main()
{
   node *R = NULL;
   R = insert(R, 33);
   insert(R,12);
   insert(R, 40);
   insert(R, 36);
   insert(R, 21);
  
  
  cout << search(R, 65)->data << endl;
  
  
}
    

CodePudding user response:

When you run

cout << search(R, 65)->data << endl;

search(R, 65) returns NULL. You can't dereference NULL by doing ->data on it. You probably want:

Node* result = search(R, 65);
if (result)
{
    cout << result->data << endl;
}
else
{
    cout << "Not found" << endl;
}

CodePudding user response:

Your problem is that you are trying to access null pointer. Pointer returned from search(R,65) is null because аt last step your root->right is null. If you want to return 0 if no elements is found you can replace your last line with this:

node *result = search(R, 65);
if (result)
 cout << result->data << endl;
else 
 cout << "0" << endl;

CodePudding user response:

Below is a working example. I have added some comments that show what things you can change in the above program to make it safe or better.

#include<iostream>
struct node
{
//always initialize built-in type data members  
int data = 0;//initialize any built in type otherwise it will have garbage value
  node* left = nullptr;//initialize any built type as stated above
  node* right = nullptr;//initialize any built in type as stated above
  
  node(int d)
  {
    data = d; 
    left = right = nullptr;

  }

};

node* insert(node *root, int n)
{
  if(root == nullptr)
  {
    return new node(n);
  }
  else
  {
    node* y;

    if(n <= root->data)
    {
      y = insert(root->left, n);
      root->left = y;
    }
    else
    {
      y = insert(root->right, n);
      root->right = y;
    }

    return root;
  }

}

node* search(node *root,int n)
{
  if(root == nullptr || root->data == n)
  {
    return root;
  }
  
  if(root->data < n)
  {
    return search(root->right, n);
  }
  return search(root->left, n);
}

int treemax(node *root)
{
   while(root->right != nullptr)
   {
     root = root->right;
   }
   return root->data;
}

int treemin(node *root)
{
  while(root->left != nullptr)
  {
    root = root->left;
  }
  return root->data;
}

int main()
{
   node *R = nullptr;
   R = insert(R, 33);
   insert(R,12);
   insert(R, 40);
   insert(R, 36);
   insert(R, 21);
  
  
  //std::cout << search(R, 65)->data << std::endl;
    node *value = search(R, 65);
    
    //check if the pointer is valid
    if(value)
    {
        std::cout<< value->data <<std::endl;
    }
    else 
    {
        std::cout<<"cannot access nullptr"<<std::endl;
    }
    
  
  
}    

The error was because search(R, 65); was returning NULL and you were trying to access a NULL pointer's data member value.

  • Related