Deletion of a node in a BST

The problem, simply

You get a binary search tree (BST): at every spot, the left side holds smaller numbers and the right side holds bigger numbers. You also get a key.

Remove the spot that holds the key. The tree must still follow the rule afterwards. Give back the top of the tree, because the top itself might be the one that got removed. If the key is not in the tree, give the tree back unchanged.

A story to remember it

Picture it

Examples

Way 1: the simple way

Pour every number out in sorted order, skip the key, and build a brand new tree from the sorted list.

1. Walk the tree left, then me, then right. This gives the numbers in sorted order. Skip the key.
2. Build a new tree from the sorted list: the middle number is the top, the left half builds the left side, the right half builds the right side.

import java.util.*;

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        List<Integer> sorted = new ArrayList<>();
        collect(root, key, sorted);
        return build(sorted, 0, sorted.size() - 1);
    }

    // left, me, right gives sorted order; leave out the key
    private void collect(TreeNode node, int key, List<Integer> out) {
        if (node == null) return;
        collect(node.left, key, out);
        if (node.val != key) out.add(node.val);
        collect(node.right, key, out);
    }

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

How long it takes: we touch every number twice, O(n). Extra room: the list of all numbers, O(n). It also gives back a different shape than the original tree, which many interviewers do not accept.

Way 2: the clever way

Find the key the BST way (smaller goes left, bigger goes right). When you find it, there are three cases.

1. No children: replace the spot with null.
2. One child: replace the spot with that child.
3. Two children: find the smallest number on the right side (go right once, then left as far as you can). That number is called the inorder successor. Copy it into the spot, then delete it from the right side. It has no left child, so that second delete is case 1 or case 2.

The function returns the new top of whatever part of the tree it was given, and each parent hooks that result back in. That is how a removed child gets replaced without any special parent tracking.

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;                   // key not found
        if (key < root.val) {
            root.left = deleteNode(root.left, key);      // fix the left side, hook it back
        } else if (key > root.val) {
            root.right = deleteNode(root.right, key);    // fix the right side, hook it back
        } else {
            if (root.left == null) return root.right;    // no child, or only a right child
            if (root.right == null) return root.left;    // only a left child
            TreeNode succ = root.right;                  // two children:
            while (succ.left != null) succ = succ.left;  // smallest on the right side
            root.val = succ.val;                         // copy it up
            root.right = deleteNode(root.right, succ.val); // remove the old copy
        }
        return root;
    }
}

How long it takes: one walk down to the key, then one walk down to the successor, both no longer than the height, O(h). Extra room: the recursion is O(h) deep. It is O(log n) for a balanced tree and O(n) for a stick.

Watch out for

• The leaf case is already covered by if (root.left == null) return root.right;, since root.right is null too.
• Removing the top. The function returns the new top, so the caller must use the return value.
• Copying the successor value and then deleting key again from the right side. You must delete succ.val, not key.
• Some interviewers want real nodes moved, not values copied (for example when a node carries other data). Then you unhook the successor and relink its children instead of copying val.

What interviewers ask next

• Can you use the predecessor instead? Yes. Take the biggest number on the left side (go left once, then right as far as you can). Both keep the rule. Alternating between them keeps the tree a little more even.
• Do it without recursion. Walk down with parent and curr. When found, compute the replacement subtree and hook it to parent.left or parent.right, or make it the new root if parent is null. That uses O(1) extra room.
• What if many deletes make the tree lopsided? Use a self balancing tree (AVL or red black) that rotates after each delete to keep the height near log n.
• Delete every node whose value is outside a range [lo, hi]. If a node is too small, return the trimmed right side. If too big, return the trimmed left side. Otherwise trim both children. O(n).

Remember this

Grown-up words: the pyramid is a BST, a kid with nobody on top is a leaf node, sliding the only child down is splicing, the lightest kid on the right is the inorder successor, and returning the new top so the parent can hook it back is the "return the new subtree root" recursion pattern.