C++ Binary Search Tree error with deleting nodes

Question

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;
      }
   }

deebee · Accepted Answer · 2012-04-28 02:13:25Z

1

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.

answered Apr 28, 2012 at 2:13

deebee

1,74713 silver badges14 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Tyler Gavin Over a year ago

this worked, and i had forgotten to set root to the new top node when deleting the previous root. stupid mistake

Collectives™ on Stack Overflow

C++ Binary Search Tree error with deleting nodes

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related