Question

(C++) Hey, so I'm trying to make a Remove() and Add() function for a Binary Search Tree (NOT USING RECURSION), can you help? For 3 cases: no child, 1 child and 2 children also for Remove().

This is the function to find the node to be deleted/added

TreeNode* PrivateFind(const T& tWhat)
   {
       //Start from head
       TreeNode* tWalk = mHead;
       while (tWalk != nullptr)
       {
           //If found then return the pointer
           if (tWalk->mData == tWhat) {
               return tWalk;
           }
           //If the current value is smaller than the target
           else if (tWalk->mData < tWhat) {
          
               //No more node
               if (tWalk == nullptr) {
                   return tWalk;
               }
               //Go right
               else {
                   tWalk = tWalk->mRight;
               }
              
           }
           //Same as above but go left
           else if (tWalk->mData > tWhat) {
              
              
               if (tWalk == nullptr) {
                   return tWalk;
               }
               else {
                   tWalk = tWalk->mLeft;
               }
               }
       }

   }

My Add function in case I did wrong in Add()

void Add(T tWhat)
   {
       //For the first node get added (root node)
       if (mHead == nullptr)
       {
           mHead = new TreeNode(tWhat);
           return;
       }
       //Find the target node
       TreeNode* tWalker = PrivateFind(tWhat);
       if (tWalker->mData == tWhat) {
           return;

       }
       else if (tWalker->mData > tWhat) {
           tWalker->mLeft = new TreeNode(tWhat);
           tWalker->mLeft->mParent = nullptr;
          
       }
       else if (tWalker->mData < tWhat) {
           tWalker->mRight = new TreeNode(tWhat);
           tWalker->mRight->mParent = nullptr;
       }
       return;
   }

this is what I currently have for Remove()

void Remove(T tWhat)
   {

       //Find the node we want to delete
       TreeNode* tWalker = PrivateFind(tWhat);
      
       if (tWalker == nullptr) {
           return;
       }
       //Case1 : no children
       if (tWalker->mLeft == nullptr && tWalker->mRight == nullptr) {
           //Special case: Delete root node
           if (tWalker == mHead) {
               mHead = nullptr;
               return;
           }
           //Delete tWalker from tWalker's parent
           if (tWalker->mParent->mLeft == tWalker) {
               tWalker->mParent->mLeft = nullptr;
           }
           else {
               tWalker->mParent->mRight = nullptr;
           }
           return;
       }
//Case 2: 1 children
       //Has children on the left
       if (tWalker->mRight == nullptr)
       {
           if (tWalker == mHead) // Special case
           {
               mHead = mHead->mLeft;
               return;
           }
           //Link tWalker's left child to tWalker's parent child
           if (tWalker->mParent->mLeft == tWalker)
               tWalker->mParent->mLeft = tWalker->mLeft;
      
           else
               tWalker->mParent->mRight = tWalker->mLeft;
      

           return;
       }
       //Has children on the right
       if (tWalker->mLeft == nullptr)
       {
           if (tWalker == mHead) // Special case
           {
               mHead = mHead->mRight;
               return;
           }
           //Link tWalker's right child as tWalker's parent child
           if (tWalker->mParent->mLeft == tWalker)
               tWalker->mParent->mLeft = tWalker->mRight;
           else {
               tWalker->mParent->mRight = tWalker->mRight;
           }
           return;
       }
//Case3 :2 children

       //Special case: the right node of tWalker is the tSucc
       //Replace tWalker with tWalker->mRight
       //For case 3: the ponter to the node in the right subtree that has minimun value
  
       TreeNode* tSucc = tWalker->mRight;
       TreeNode* tSuccParent = tWalker; //tSucc's parent
      
       if (tSucc->mLeft == nullptr) {
           tWalker->mData = tSucc->mData;
           tWalker->mRight = tSucc->mRight;
           return;
       }
       while (tSucc->mLeft != nullptr) {
           tSuccParent = tSucc;
           tSucc = tSucc->mLeft;
       }
       tWalker->mData = tSucc->mData;
       tSuccParent->mLeft = tSucc->mRight;

}

Answer 1

Hey, i checke your code, actually you are missing some corner cases and due to which you unwantedly extended your solution,

I can help you with precise solution, with all corner cases checked.

struct BSTNode {

    int key;

    struct BSTNode *left, *right;

};

// Utitlity function to create a new node

BSTNode* newNode(int data)

{

BSTNode* temp = new BSTNode;

    temp->key = data;

    temp->left = NULL;

    temp->right = NULL;

    return temp;

}

// A utility function to insert a new

// Node with given key in BST

BSTNode* insert(BSTNode* root, int key)

{

    // Create a new Node containing

    // the new element

BSTNode* newnode = newNode(key);

    // Pointer to start traversing from root and

    // traverses downward path to search

    // where the new node to be inserted

BSTNode* a = root;

    // Pointer y maintains the trailing

    // pointer of a

BSTNode* b = NULL;

    while (a != NULL) {

b = a;

        if (key < a->key)

a = a->left;

        else

a = a->right;

    }

    // If the root is NULL i.e the tree is empty

    // The new node is the root node

    if (b == NULL)

        y = newnode;

    // If the new key is less then the leaf node key

    // Assign the new node to be its left child

    else if (key < b->key)

b->left = newnode;

    // else assign the new node its right child

    else

b->right = newnode;

    // Returns the pointer where the

    // new node is inserted

    return b;

}

REMOVE FUNCTION

This function is a bit complex, but if you try to understand with example you will get it.

BSTNode* deleteIterative(BSTNode* root, int key)

{

BSTNode* curr = root;

BSTNode* prev = NULL;

    // Check if the key is actually

    // present in the BST.

    // the variable prev points to

    // the parent of the key to be deleted.

    while (curr != NULL && curr->data != key) {

        prev = curr;

        if (key < curr->data)

            curr = curr->left;

        else

            curr = curr->right;

    }

    if (curr == NULL) {

        cout << "Key " << key

             << " not found in the"

             << " provided BST.\n";

        return root;

    }

    // Check if the node to be

    // deleted has atmost one child.

    if (curr->left == NULL

        || curr->right == NULL) {

        // newCurr will replace

        // the node to be deleted.

BSTNode* newCurr;

        // if the left child does not exist.

        if (curr->left == NULL)

            newCurr = curr->right;

        else

            newCurr = curr->left;

        // check if the node to

        // be deleted is the root.

        if (prev == NULL)

            return newCurr;

        // check if the node to be deleted

        // is prev's left or right child

        // and then replace this with newCurr

        if (curr == prev->left)

            prev->left = newCurr;

        else

            prev->right = newCurr;

        // free memory of the

        // node to be deleted.

        free(curr);

    }

    // node to be deleted has

    // two children.

    else {

BSTNode* p = NULL;

BSTNode* temp;

        // Compute the inorder successor

        temp = curr->right;

        while (temp->left != NULL) {

            p = temp;

            temp = temp->left;

        }

        // check if the parent of the inorder

        // successor is the root or not.

        // if it isn't, then make the

        // left child of its parent equal to the

        // inorder successor's right child.

        if (p != NULL)

            p->left = temp->right;

        // if the inorder successor was the

        // root, then make the right child

        // of the node to be deleted equal

        // to the right child of the inorder

        // successor.

        else

            curr->right = temp->right;

        curr->data = temp->data;

        free(temp);

    }

    return root;

}

Hope i helped you.

Happy Learning.