How can i delete from webb search?

How do I delete a node in a binary search tree?

• I have written this code but it's not working. Kindly tell me the problem. template <class T> void bst<T>::delete_node(T key1) { bst_node<T>* p = search(key1); if (p) { if (p->parent) { if (p->left == NULL && p->right == NULL) { if (p->parent->key > key1) { p->parent->left = NULL; delete p; } else { p->parent->right = NULL; delete p; } } else if (p->left != NULL && p->right == NULL) { if (p->parent->key > key1) { p->parent->left = p->left; p->left->parent = p->parent; delete p; } else { p->parent->right = p->left; p->left->parent = p->parent; delete p; } } else if (p->left == NULL && p->right != NULL) { if (p->parent->key > key1) { p->parent->left = p->right; p->right->parent = p->parent; delete p; } else { p->parent->right = p->right; p->right->parent = p->parent; delete p; } } else if (p->left != NULL && p->right != NULL) { T key2 = searchMinRight(p->right); p->key = key2; delete_node(key2); } } else { if (p->left != NULL && p->right == NULL) { p->left->parent = NULL; delete p; } else if (p->left == NULL && p->right != NULL) { p->right->parent = NULL; delete p; } else if (p->left != NULL && p->right != NULL) { T key2 = searchMinRight(p->right); p->key = key2; delete_node(key2); } } } }

• Answer:

  Three cases are possible for the node to be deleted: 1) Leaf Node - You can simply delete the node by pointing the corresponding pointer(left or right) of the parent of node to NULL. 2) Node with 1 child - Replace the pointer of the current node with its only child(left / right). 3) Node with 2 children - Select one of the following- A) Go one right and then move to leftmost node B) Go one left and then move to rightmost node Choose any one of A & B and replace the value of node to be deleted by the value of chosen node(A or B). Then delete the chosen node as per step 1(Leaf Node)