Part 7 of 15 in Binary Search Trees

## Delete a node from binary search tree by animeshn

Problem statement

Write a function to delete for a Node with a given data in a binary search tree. A binary search tree is a binary tree in which value of all the nodes left of a node are lesser than it and value of all the nodes right of node are greater than it. You may assume that there are no duplicate values in the tree. In case the node to be deleted has both children, the strategy to adopt is to replace that node with the maximum value in its left subtree (lets call it MAX_LEFT). Then you can simply delete the node MAX_LEFT. This strategy is also discussed in our video for this problem.

Input

You need to write a function named "DeleteNodeInBST" that will take root of a binary search tree and the data of the node to be deleted as arguments.

Output

Your function must return pointer to root of the tree after deletion. Make sure that the resultant tree is still a BST. Also note, that there may be no nodes at all with the given data in the tree, in which case you should simply return the tree without modification.