# Tech Interview Exam Question: Delete Node in a BST (Hard Core!)

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

Search for a node to remove.
If the node is found, delete the node.
Note: Time complexity should be O(height of tree).

Example:

root = [5,3,6,2,4,null,7]
key = 3

5
/ \
3 6
/ \ \
2 4 7

Given key to delete is 3. So we find the node with value 3 and delete it.

One valid answer is [5,4,6,2,null,null,7], shown in the following BST.

5
/ \
4 6
/ \
2 7

5
/ \
2 6
\ \
4 7
Accepted
66,103
Submissions
165,217

```
/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {number} key
* @return {TreeNode}
*/
var deleteNode = function(root, key) {

var node = root;
var nodeParent = root;
var childReference = null;

//Find the node with key
while(node !== null){
if(node.val === key){
break;
}
else if(node.val < key){
nodeParent = node;
node = node.right;
childReference = 'right';
}
else{
nodeParent = node;
node = node.left;
childReference = 'left';
}
}

//If node is not in the tree
if(node === null) return root;

//If node is a leaf
if(node.left === null && node.right === null){
if(childReference === null) return null;//Root node matches the key
nodeParent[childReference] = null;
}
//If node is has one child
else if(node.left === null){
if(childReference === null) return node.right;//Root node matches the key
nodeParent[childReference] = node.right;

}
else if(node.right === null){
if(childReference === null) return node.left;//Root node matches the key
nodeParent[childReference] = node.left;
}
//If node is has both children
else{
var value = findMinNode(node.right);
node.val = value;
node.right = deleteNode(node.right,value);
}

return root;

};

var findMinNode = function(node){
if(node === null) return false;
while(node.left !== null){
node = node.left;
}
return node.val;
}

```

I spent the whole morning on this and this is the result I got from the leetcode:

Runtime: 92 ms, faster than 86.76% of JavaScript online submissions for Delete Node in a BST.

Memory Usage: 42.2 MB, less than 32.28% of JavaScript online submissions for Delete Node in a BST.