Question

27 Page of 50 ZOOM BST Algorithms - Delete (6) 27 SUBROUTINE deleteNode(node, parent): IF node.left and node.right are null IF parent is null root = null Case1 ELSE set parent.link to null (link is either left or right child) END IF Case 3 ELSE IF node. left is null set parent.link to node.right (link is either left or right child) ELSE IF node.right is null set parent.link to node.left (link is either left or right child) Case 4 Case 2 ELSE replace node value with max value of left subtree set max node's parent's right child to max node's left child delete max node END IF END SUBROUTINE

I need help to write this code in C++, I am struggling to find max node's parent's right child and max node's left child.

Node* maxValueNode(Node* node)
{
   Node* current = node;
   while (current && current->right != NULL)
       current = current->right;
   return current;
}

void deleteNode(BST* tree, Node* node, Node* parent)
{
   //TODO - follow the lecture pseudocode to write the deleteNode function
   // - returns true if the value was deleted, false if not
   // - don't forget to free the memory for the node you're deleting
   if (node->left == NULL && node->right == NULL)
   {
       if (parent == NULL)
           tree->root = NULL;
       else
           parent->left = NULL;
   }
   else if (node->left == NULL)
       parent->left = node->right;
   else if (node->right == NULL)
       parent->right = node->left;
   else
   {
       Node* max = maxValueNode(node->left);
       node->value = max->value;

Here is my current work.

Answer 1

Program that follows the pseudocode and answer your question accordingly to the program-

#include <iostream>
using namespace std;

// Data structure to store a Binary Search Tree node
struct Node {
   int data;
   Node *left, *right;
};

// Function to create a new binary tree node having given key
Node* newNode(int key)
{
   Node* node = new Node;
   node->data = key;
   node->left = node->right = nullptr;

   return node;
}

// Function to perform inorder traversal of the BST
void inorder(Node *root)
{
   if (root == nullptr)
       return;

   inorder(root->left);
   cout << root->data << " ";
   inorder(root->right);
}

// Helper function to find minimum value node in subtree rooted at curr
Node* maxValueNode(Node* node)
{
Node* current = node;
while (current && current->right != NULL)
current = current->right;
return current;
}

// Recursive function to insert an key into BST
Node* insert(Node* root, int key)
{
   // if the root is null, create a new node an return it
   if (root == nullptr)
       return newNode(key);

   // if given key is less than the root node, recur for left subtree
   if (key < root->data)
       root->left = insert(root->left, key);

   // if given key is more than the root node, recur for right subtree
   else
       root->right = insert(root->right, key);

   return root;
}

// Iterative function to search in subtree rooted at curr & set its parent
// Note that curr & parent are passed by reference
void searchKey(Node* &curr, int key, Node* &parent)
{
   // traverse the tree and search for the key
   while (curr != nullptr && curr->data != key)
   {
       // update parent node as current node
       parent = curr;

       // if given key is less than the current node, go to left subtree
       // else go to right subtree
       if (key < curr->data)
           curr = curr->left;
       else
           curr = curr->right;
   }
}

// Function to delete node from a BST
bool deleteNode(Node*& root, int key)
{
   // pointer to store parent node of current node
   Node* parent = nullptr;

   // start with root node
   Node* curr = root;

   // search key in BST and set its parent pointer
   searchKey(curr, key, parent);

   // return if key is not found in the tree
   if (curr == nullptr)
       return false;

   // Case 1: node to be deleted has no children i.e. it is a leaf node
   if (curr->left == nullptr && curr->right == nullptr)
   {
       // if node to be deleted is not a root node, then set its
       // parent left/right child to null
       if (curr != root)
       {
           if (parent->left == curr)
               parent->left = nullptr;
           else
               parent->right = nullptr;
       }
       // if tree has only root node, delete it and set root to null
       else
           root = nullptr;

       // deallocate the memory
       free(curr);   // or delete curr;
       return true;
   }

   // Case 2: node to be deleted has two children
   else if (curr->left && curr->right)
   {
       // find its in-order successor node
       Node* successor = maxValueNode(curr->left);

       // store successor value
       int val = successor->data;

       // recursively delete the successor. Note that the successor
       // will have at-most one child (right child)
       deleteNode(root, successor->data);

       // Copy the value of successor to current node
       curr->data = val;
   }

   // Case 3: node to be deleted has only one child
   else
   {
       // find child node
       Node* child = (curr->left)? curr->left: curr->right;

       // if node to be deleted is not a root node, then set its parent
       // to its child
       if (curr != root)
       {
           if (curr == parent->left)
               parent->left = child;
           else
               parent->right = child;
       }

       // if node to be deleted is root node, then set the root to child
       else
           root = child;

       // deallocate the memory
       free(curr);
       return true;
   }
}

// main function
int main()
{
   Node* root = nullptr;
   bool x;
   int keys[] = { 15, 10, 20, 8, 12, 16 };

   for (int key : keys)
       root = insert(root, key);

   x = deleteNode(root, 1);
   if(x == true)
cout<<"Deleted Successfully"<<endl;
   else
cout<<"Not deleted key not found"<<endl;
   inorder(root);

   return 0;
}