Delete a Node From a Binary Search Tree

medium bst tree recursion

Problem

Remove the node with the given value from a BST and return the new root. The deleted node is replaced by null when it has no child, by its only child when it has one, or by its in-order successor (smallest in the right subtree) when it has two children.

InputBST = [5, 3, 6, 2, 4, _, 7], v = 3

OutputBST = [5, 4, 6, 2, _, _, 7]

3 has two children; replace with successor 4, then delete 4 from the right subtree.

BST (level-order)

def delete_bst(root, v):
    if root is None: return None
    if v < root.val: root.left = delete_bst(root.left, v)
    elif v > root.val: root.right = delete_bst(root.right, v)
    else:
        if root.left is None: return root.right
        if root.right is None: return root.left
        succ = root.right
        while succ.left: succ = succ.left
        root.val = succ.val
        root.right = delete_bst(root.right, succ.val)
    return root

function deleteBST(root, v) {
  if (!root) return null;
  if (v < root.val) root.left = deleteBST(root.left, v);
  else if (v > root.val) root.right = deleteBST(root.right, v);
  else {
    if (!root.left) return root.right;
    if (!root.right) return root.left;
    let succ = root.right; while (succ.left) succ = succ.left;
    root.val = succ.val;
    root.right = deleteBST(root.right, succ.val);
  }
  return root;
}

class Solution {
    public TreeNode deleteBST(TreeNode root, int v) {
        if (root == null) return null;
        if (v < root.val) root.left = deleteBST(root.left, v);
        else if (v > root.val) root.right = deleteBST(root.right, v);
        else {
            if (root.left == null) return root.right;
            if (root.right == null) return root.left;
            TreeNode succ = root.right; while (succ.left != null) succ = succ.left;
            root.val = succ.val;
            root.right = deleteBST(root.right, succ.val);
        }
        return root;
    }
}

TreeNode* deleteBST(TreeNode* root, int v) {
    if (!root) return nullptr;
    if (v < root->val) root->left = deleteBST(root->left, v);
    else if (v > root->val) root->right = deleteBST(root->right, v);
    else {
        if (!root->left) return root->right;
        if (!root->right) return root->left;
        TreeNode* succ = root->right; while (succ->left) succ = succ->left;
        root->val = succ->val;
        root->right = deleteBST(root->right, succ->val);
    }
    return root;
}

Time: O(h) Space: O(h)