Delete Node in a BST

Share

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

Example 1
Input: root=[5,3,6,2,4,null,7], key=3 → Output: [5,4,6,2,null,null,7]
Example 2
Input: root=[5,3,6,2,4,null,7], key=0 → Output: [5,3,6,2,4,null,7]

Solution Approach

Three cases for deletion: (1) node has no children, just remove; (2) node has one child, replace with that child; (3) node has two children. Replace with the inorder successor (smallest in right subtree) and delete successor.

  • Search for the key recursively.
  • If key < root.val: root.left = delete(root.left, key).
  • If key > root.val: root.right = delete(root.right, key).
  • If key == root.val: if no left child return right; if no right child return left; else find min in right subtree, set root.val = min.val, delete min from right subtree.
Java
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;
        if (key < root.val) root.left = deleteNode(root.left, key);
        else if (key > root.val) root.right = deleteNode(root.right, key);
        else {
            if (root.left == null) return root.right;
            if (root.right == null) return root.left;
            TreeNode min = root.right;
            while (min.left != null) min = min.left;
            root.val = min.val;
            root.right = deleteNode(root.right, min.val);
        }
        return root;
    }
}
  • Time Complexity: O(H) where H is height; O(log N) for balanced BST
  • Space Complexity: O(H) recursion stack