Time: 30 minutes

The question is divided into two parts to be solved, search and delete

The search part is to find the node. You can find the required node according to the properties of the binary search tree.

There are three types of deletion

  1. If there is only a left child, replace it with the left child.
  2. If there is only a right child, replace it with the right child.
  3. If there is neither child, assign null. (Since there was a recursive assignment earlier, this will succeed.)
  4. If there are both children, store the left child, replace it with the right child, and then find the left child’s position on the right.
var deleteNode = function(root, key) {
    function  insert(root,node) {
        if (root.val > node.val) {
            if (!root.left) {
                root.left = node
            } else {
                insert(root.left,node)
            }
        } else {
            if (!root.right) {
                root.right = node
            } else {
                insert(root.right,node)
            }
        }
    }
    function search(root) {
      if (!root) {
        return null
      }
        if (root.val > key) {
            root.left = search(root.left)
        } else if (root.val < key){
            root.right = search(root.right)
        }  else {
            if (!root.left && !root.right) {
                root = null            } else if (root.left && root.right) {
                var left = root.left                root = root.right                insert(root,left)
            }
            else if (root.left) {
                root = root.left            } else if (root.right) {
                root = root.right            }
        }
        return root    }
    return search(root)
};

Points to note

  1. Consider the case where the node does not exist.
  2. To delete a node, assign the left (or right) node the return value of the recursion.