CODEWITHSUNDEEP
c++binary-search-tree
Sebastian Miodek
Sebastian Miodek

Reputation: 23

Binary Search Tree - Deleting Node with no pointer to predecessor

I have following implementation of BST:

struct BstNode
{
    int value;
    BstNode* leftSubnode;
    BstNode* rightSubnode;

    BstNode(int value)
    {
        this->value = value;
        this->leftSubnode = this->rightSubnode = nullptr;
    }
};

struct BstTree
{
    BstNode* root;
};

and you can see, that I have no pointer to predecessor (the parent of current node). I have no problem with implementing adding/displaying methods, but I can't figure out how to remove a node from my structure. Is there any possibility to do it when you have only pointers to left and right node? Please notice, that all methods should be implemented for the BstTree structure, not for the BstNode one (because of the task that I received from my teacher).

Upvotes: 1

Views: 1536

Answers (1)

john
john

Reputation: 87944

Something like this, adapt to your particular requirements and fill in the blanks

void remove(BstTree& tree, int value)
{
   BstNode* parent = nullptr;
   BstNode* node = tree.root;
   while (node)
   {
      if (node->value == value)
      {
         if (parent)
         {
            // remove node using the parent pointer
         }
         else
         {
            // remove the root node
         }
         return;
      }
      if (value < node->value)
      {
         // go down left branch
         parent = node;
         node = node->leftSubNode;
      }
      else
      {
         // go down right branch
         parent = node;
         node = node->rightSubNode;
      }
   }
}

Upvotes: 2

Related Questions