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

Another valid answer is [5,2,6,null,4,null,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.