Delete Node in a BST

medium bst tree recursion

Problem

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.

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_node(root, v):
    if root is None: return None
    if v < root.val: root.left = delete_node(root.left, v)
    elif v > root.val: root.right = delete_node(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_node(root.right, succ.val)
    return root

function deleteNode(root, v) {
  if (!root) return null;
  if (v < root.val) root.left = deleteNode(root.left, v);
  else if (v > root.val) root.right = deleteNode(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 = deleteNode(root.right, succ.val);
  }
  return root;
}

class Solution {
    public TreeNode deleteNode(TreeNode root, int v) {
        if (root == null) return null;
        if (v < root.val) root.left = deleteNode(root.left, v);
        else if (v > root.val) root.right = deleteNode(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 = deleteNode(root.right, succ.val);
        }
        return root;
    }
}

TreeNode* deleteNode(TreeNode* root, int v) {
    if (!root) return nullptr;
    if (v < root->val) root->left = deleteNode(root->left, v);
    else if (v > root->val) root->right = deleteNode(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 = deleteNode(root->right, succ->val);
    }
    return root;
}

Explanation

Deleting from a binary search tree happens in two stages: first find the node, then splice it out without breaking the BST ordering. Because of the BST property, finding is easy — go left when v is smaller, right when it is larger.

The deletion itself has three cases. If the node has no left child, we just return its right child to take its place. If it has no right child, we return the left child. Both of these simply pull the surviving branch up.

The interesting case is a node with two children. We can't just drop it, so instead we replace its value with its in-order successor — the smallest value in the right subtree, found by walking succ.left until it runs out. We copy that value up, then recursively delete the successor from the right subtree.

The successor is special because it is larger than everything on the left and smaller than everything else on the right, so swapping it in keeps the tree sorted.

Example: delete 3 from [5, 3, 6, 2, 4, _, 7]. Node 3 has two children, its successor is 4; we overwrite 3 with 4 and delete the old 4, giving [5, 4, 6, 2, _, _, 7].

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