CODEWITHSUNDEEP
c++binary-search-tree
Tyler Gavin
Tyler Gavin

Reputation: 117

C++ Binary Search Tree error with deleting nodes

I'm working with deleting nodes from a binary search tree and I keep getting a segfault error after the while loop in this function. Please help me catch any errors if you can.

Here is the function:

void deleteNode()
   {
      int key;
      nodePtr location = NULL, parent = NULL;

      cout << "Enter account number to delete: ";
      cin >> key;
      cout << endl << endl;

      bool found = searchTree(key, &location, &parent);

      if (!found)
      {
         cout << "Error! Account number: " << key << " was not found."
         << endl << endl;
      }
      else if (location->left != NULL && location->right != NULL)
      {  //delete node with left and right subtrees
         nodePtr leftmost = location->right, leftmostParent = NULL;

         while (leftmost->left != NULL)
         {
            leftmostParent = leftmost;
            leftmost = leftmost->left;
         }

         leftmost->left = location->left;

         if (location->right != leftmost)
            leftmost->right = location->right; cout << "1" << endl;

         if (parent != NULL)
         {
            if (parent->acctNum > location->acctNum)
               parent->left = leftmost;
            else
               parent->right = leftmost;
         }

         leftmostParent->left = NULL;

         delete location;
         location = NULL;
      }
      else if (location->left != NULL && location->right == NULL)
      {  //delete node with only a left subtree
         if (parent->acctNum > location->acctNum)
            parent->left = location->left;
         else
            parent->right = location->left;

         delete location;
         location = NULL;
      }
      else if (location->left == NULL && location->right != NULL)
      {  //delete node with only a right subtree
         nodePtr leftmost = location->right, leftmostParent = NULL;

         while (leftmost->left != NULL)
         {
            leftmostParent = leftmost;
            leftmost = leftmost->left;
         }

         leftmost->right = location->right;
         leftmostParent->left = NULL;

         if (parent->acctNum > location->acctNum)
            parent->left = leftmost;
         else
            parent->right = leftmost;

         delete location;
         location = NULL;
      }
      else
      {  //delete a leaf node
         if (location->acctNum > parent->acctNum)
            parent->right = NULL;
         else
            parent->left = NULL;

         delete location;
         location = NULL;
      }
   }

Upvotes: 0

Views: 497

Answers (1)

deebee
deebee

Reputation: 1747

I see one problem here 

nodePtr leftmost = location->right, leftmostParent = NULL;

while (leftmost->left != NULL)
{
    leftmostParent = leftmost;
    leftmost = leftmost->left;
} 
...

leftmostParent->left = NULL;

if location->right is a leaf, then leftmostParent is never set and still pointing to NULL; so will segfault.

Upvotes: 1

Related Questions