//main.cpp #include <iostream> using namespace std; // Definition for a binary t
ID: 3861680 • Letter: #
Question
//main.cpp
#include <iostream>
using namespace std;
// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) {
left = NULL;
right = NULL;
val = x;
}
};
TreeNode * deleteNode(TreeNode* root, int key) {
// your code here
return root;
}
void inorderPrint(TreeNode* node)
{
if (!node) return;
inorderPrint(node->left);
cout << node->val << " ";
inorderPrint(node->right);
}
void deleteTree(TreeNode* root)
{
if (root == NULL) return;
deleteTree(root->left);
deleteTree(root->right);
delete root;
root = NULL;
}
int main() {
/*
* Example 1: Deleting a leaf node
* key = 14
* 9
* /
* 5 12
* / /
* 2 7 10 14
*
* After deleteNode(14):
* 9
* /
* 5 12
* / /
* 2 7 10
*
* Example 2: Deleting a node which has only
* one child.
* 9
* /
* 5 12
* / /
* 2 7 10
*
* After deleteNode(12):
* 9
* /
* 5 10
* /
* 2 7
*
* Example 3: Deleting a node with 2 children
* After deleteNode(5):
* Method 1 (IOS)
* 9
* /
* 7 10
* /
* 2
*
* Method 2 (IOP)
* 9
* /
* 2 10
*
* 7
*/
TreeNode * root = new TreeNode(9);
root->left = new TreeNode(5);
root->right = new TreeNode(12);
root->left->left = new TreeNode(2);
root->left->right = new TreeNode(7);
root->right->left = new TreeNode(10);
root->right->right = new TreeNode(14);
cout << "Before deleting a leaf: " << endl;
inorderPrint(root);
cout << endl;
root = deleteNode(root, 14);
cout << "After deleting a leaf: " << endl;
inorderPrint(root);
cout << endl;
cout << "Before deleting a node with 1 child: " << endl;
inorderPrint(root);
cout << endl;
root = deleteNode(root, 12);
cout << "After deleting a node with 1 child: " << endl;
inorderPrint(root);
cout << endl;
cout << "Before deleting a node with 2 child: " << endl;
inorderPrint(root);
cout << endl;
root = deleteNode(root, 5);
cout << "After deleting a node with 2 child: " << endl;
inorderPrint(root);
cout << endl;
deleteTree(root);
return 0;
}
The Problem Complete the deleteNode function that accepts a BST TreeNode :k and a key, and returns the root node of the updated BST. Note that the correct implementation will print the increasing inorder list after removal. There are 3 types of removal you would need to take care of: Example 1 (remove a leaf: key 14 5 12 2 7 10 14 After deleteNode (14) 5 12 2 7 10 Example 2 (remove a node with 1 child): key 12 5 12 2 7 10 After deleteNode (12): 5 10 2 7 Example 3 (remove a node with 2 children): key 59 /15 10 A. 27 After deleteNode(5): / 10Explanation / Answer
TreeNode* deleteNode(TreeNode* root, int key){
if(root == NULL) return root;
else if(key < root->val) root->left = deleteNode(root->left,key);
else if(key) root->right = deleteNode(root->right, key);
else {
// Case 1: No Child
if(root->left == NULL && root->right == NULL){
delete root;
root = NULL;
// Case 2: one child
} else if(root->left == NULL){
struct Node *temp = root;
root = root->right;
delete temp;
} else if(root->right == NULL){
struct Node *temp = root;
root = root->left;
delete temp;
//Case 3: two child
} else{
struct Node *temp = FindMin(root->right);
root->val = temp->val;
root->right = deleteNode(root->right, temp->val);
}
}
return root;
}
//This is required in deleteNode function
TreeNode* FindMin(TreeNode* root){
while(root->left != NULL) root = root->left;
return root;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.