Delete Node in a BST

NeetCode: Delete Node in a BST · LeetCode: 450. Delete Node in a BST · Difficulty: Medium

Given the root of a BST and a key, delete the node with that key if it exists, and return the (possibly new) root. The result must still be a valid BST. If the key is absent the tree is unchanged.

Example

Text

Input:  [5, 3, 6, 2, 4, null, 7], key = 3
Output: 5,4,2,N,N,N,6,N,7,N,N   (preorder; 3 is replaced by 4, its inorder successor)
            5                5
           / \              / \
          3   6     ->     4   6
         / \   \          /     \
        2   4   7        2       7

Several valid trees exist for the same deletion. The programs print the inorder listing (sorted values without the key), which is identical for every valid answer; the optimal one also prints its exact shape.

Trees are given in LeetCode's level-order array form: the first value is the root, and each following pair of values holds the left and right child of the next node that exists, in the order the nodes were placed. null marks a missing child, and a missing node has no children listed. The tree(Integer...) helper in each program builds a TreeNode from such an array. TreeNode has the fields val, left, and right; a missing child is null, so no wrapper type is needed.

Brute force: rebuild from a sorted list

Read the values in order, drop the key, and rebuild a balanced BST from the sorted list. removeIf removes every element that matches a condition. The lambda compares an Integer element with the int key, which unboxes the element, so the comparison is by value.

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    private void inorder(TreeNode node, List<Integer> out) {
        if (node == null) {
            return;
        }
        inorder(node.left, out);
        out.add(node.val);
        inorder(node.right, out);
    }

    private TreeNode build(List<Integer> sorted, int lo, int hi) { // sorted[lo, hi)
        if (lo >= hi) {
            return null;
        }
        int mid = lo + (hi - lo) / 2;
        TreeNode node = new TreeNode(sorted.get(mid));
        node.left = build(sorted, lo, mid);
        node.right = build(sorted, mid + 1, hi);
        return node;
    }

    public TreeNode deleteNode(TreeNode root, int key) {
        List<Integer> values = new ArrayList<>();
        inorder(root, values);
        values.removeIf(v -> v == key); // v is unboxed and compared with the int key
        return build(values, 0, values.size());
    }
}

public class Main {
    // Builds a tree from LeetCode's level-order array: null marks a missing child.
    static TreeNode tree(Integer... values) {
        if (values.length == 0 || values[0] == null) {
            return null;
        }
        TreeNode root = new TreeNode(values[0]);
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode node = queue.remove();
            if (i < values.length && values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    static void inorder(TreeNode node, List<Integer> out) {
        if (node == null) {
            return;
        }
        inorder(node.left, out);
        out.add(node.val);
        inorder(node.right, out);
    }

    static void run(Integer[] values, int key) {
        TreeNode result = new Solution().deleteNode(tree(values), key);
        List<Integer> out = new ArrayList<>();
        inorder(result, out);
        System.out.println(out);
    }

    public static void main(String[] args) {
        Integer[] bst = {5, 3, 6, 2, 4, null, 7};
        run(bst, 3);
        run(bst, 0);
        run(new Integer[] {}, 0);
        run(new Integer[] {1}, 1);
    }
}

Output

[2, 4, 5, 6, 7]
[2, 3, 4, 5, 6, 7]
[]
[]

Valid, but it visits every node and rebuilds the whole tree for a single deletion. Time: O(n). Space: O(n).

Optimal: three-case deletion

Search for the key using the BST order (O(h)). When you find the node, there are three cases:

No left child: replace the node with its right subtree (this also covers leaves).
No right child: replace the node with its left subtree.
Two children: the value that can take its place without breaking the order is the inorder successor, the smallest value in the right subtree. Copy it into the current node, then delete that value from the right subtree (a recursive call that hits case 1 or 2).

The method returns the new root of the subtree, and the caller stores it back in its left or right field. The tree is changed in place, so the input tree is not usable afterwards in its original form.

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

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; // also covers a leaf
            }
            if (root.right == null) {
                return root.left;
            }
            TreeNode successor = root.right; // smallest node of the right subtree
            while (successor.left != null) {
                successor = successor.left;
            }
            root.val = successor.val;
            root.right = deleteNode(root.right, root.val);
        }
        return root;
    }
}

public class Main {
    // Builds a tree from LeetCode's level-order array: null marks a missing child.
    static TreeNode tree(Integer... values) {
        if (values.length == 0 || values[0] == null) {
            return null;
        }
        TreeNode root = new TreeNode(values[0]);
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode node = queue.remove();
            if (i < values.length && values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    static void inorder(TreeNode node, List<Integer> out) {
        if (node == null) {
            return;
        }
        inorder(node.left, out);
        out.add(node.val);
        inorder(node.right, out);
    }

    static String serialize(TreeNode root) {
        if (root == null) {
            return "N";
        }
        return root.val + "," + serialize(root.left) + "," + serialize(root.right);
    }

    static void run(Integer[] values, int key) {
        TreeNode result = new Solution().deleteNode(tree(values), key);
        List<Integer> out = new ArrayList<>();
        inorder(result, out);
        System.out.println(out + "  shape: " + serialize(result));
    }

    public static void main(String[] args) {
        Integer[] bst = {5, 3, 6, 2, 4, null, 7};
        run(bst, 3);
        run(bst, 0);
        run(new Integer[] {}, 0);
        run(new Integer[] {1}, 1);
    }
}

Output

[2, 4, 5, 6, 7]  shape: 5,4,2,N,N,N,6,N,7,N,N
[2, 3, 4, 5, 6, 7]  shape: 5,3,2,N,N,4,N,N,6,N,7,N,N
[]  shape: N
[]  shape: N

Time: O(h): one descent to find the key plus one descent to find and delete the successor. h is O(log n) for a balanced tree and O(n) for a chain. Space: O(h) for the recursion.

How to explain it in an interview

Say first: take the inorder list, drop the key, rebuild a balanced BST. It works but costs O(n) for one deletion.
Key insight: only the deleted node's spot needs fixing; with two children, the smallest node of the right subtree can take its place without breaking the ordering.
Code it in steps: (1) go left or right by comparing key with root.val; (2) on a match, handle no-left and no-right by returning the other subtree; (3) with two children copy the minimum of the right subtree into the node; (4) delete that minimum value from the right subtree.
Complexity to state: time O(h), space O(h) for recursion.
Likely follow-ups / pitfalls: the predecessor (max of left subtree) works equally well; a missing key returns the tree unchanged; assign the recursive result back to root.left or root.right, or the deletion is lost.

Interview points

Deleting a node with at most one child returns the other child in its place.
With two children, the inorder successor (or predecessor) takes the node's value, then is deleted from its subtree.
Time is O(h), which is O(n) on a chain.

Summary

Three cases: no left child, no right child, two children.
The inorder successor is the leftmost node of the right subtree.
A key that is not in the tree leaves the tree unchanged.