//main.cpp

#include

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 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

inorderPrint(root);

cout

root = deleteNode(root, 14);

cout

inorderPrint(root);

cout

cout

inorderPrint(root);

cout

root = deleteNode(root, 12);

cout

inorderPrint(root);

cout

cout

inorderPrint(root);

cout

root = deleteNode(root, 5);

cout

inorderPrint(root);

cout

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): /\7 10