Delete Node in a BST

MEDIUM✓ CHIP-TIMEDLC #450 — FULL STATEMENT ↗

The drill: Remove one value from a BST and hand back a tree that is still a valid BST — the tricky part is only the node with two children, since either neighbor can legally take its place.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A binary search tree and a key arrive together, and the task is to remove the node holding that key — if it exists — while the tree that remains still obeys BST ordering.

Removing a leaf or a node with a single child is straightforward: it simply gets spliced out. A node with two children is the interesting case, since either its inorder predecessor or its inorder successor can legally take its place without breaking the ordering.

If the key isn't present in the tree at all, the tree is handed back completely unchanged — there's nothing to remove.

EX 01

root = [5, 3, 8, 1, 4, 7, 9] · key = 1

→ [5, 3, 8, null, 4, 7, 9]

DELETE A LEAF

EX 02

root = [5, 3, 8, 1, 4, 7, 9] · key = 9

→ [5, 3, 8, 1, 4, 7]

DELETE A LEAF ON THE OTHER SIDE

EX 03

root = [5, 3, 8, 1, 4, 7, 9] · key = 3

→ [5, 4, 8, 1, null, 7, 9]

TWO-CHILD NODE, SUCCESSOR IS A LEAF

the key may or may not be present in the tree
the tree can hold anywhere from zero to a few thousand nodes
all values in the tree are unique and follow standard BST ordering
either valid neighbor may replace a two-child node's spot

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

A leaf or a one-child node is easy: splice it out and reattach its single subtree. What breaks that trick when there are two children?

HINT 2 THE STRUCTURE

You need a replacement value that keeps the ordering intact — one that sits immediately next to the deleted value in sorted order. Where does that value live structurally?

HINT 3 ONE STEP FROM THE ANSWER

The inorder successor is the leftmost node of the right subtree. Copy its value into the node being deleted, then delete that successor from the right subtree instead — a smaller, solvable version of the same problem.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE SUCCESSOR SWAPPATTERN · GUIDED DESCENTroot = [5, 3, 8, 1, 4, 7, 9] · key = 3

STEP 1

Delete key 3. It has two children, so instead of splicing it out we borrow its inorder successor's value.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/delete-node-in-a-bst.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if not root:
            return None
        if key < root.val:
            root.left = self.deleteNode(root.left, key)
        elif key > root.val:
            root.right = self.deleteNode(root.right, key)
        else:
            if not root.left:
                return root.right
            if not root.right:
                return root.left
            succ = root.right
            while succ.left:                # leftmost of the right subtree
                succ = succ.left
            root.val = succ.val
            root.right = self.deleteNode(root.right, succ.val)
        return root

TIME O(H)SPACE O(H)PYTHON · RACE PACE · 19 LN

class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if not root:
            return None
        if root.val == key:
            if not root.left:
                return root.right
            if not root.right:
                return root.left
            succ = root.right
            while succ.left:
                succ = succ.left
            root.val = succ.val
            root.right = self.deleteNode(root.right, succ.val)
            return root
        # ignore the BST ordering — walk into both children regardless
        root.left = self.deleteNode(root.left, key)
        root.right = self.deleteNode(root.right, key)
        return root

TIME O(N)SPACE O(H)PYTHON · TRAINING PACE · 19 LN

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

TIME O(H)SPACE O(H)JAVA · RACE PACE · 26 LN

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }
        if (root.val == key) {
            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;
        }
        // ignore the BST ordering — walk into both children regardless
        root.left = deleteNode(root.left, key);
        root.right = deleteNode(root.right, key);
        return root;
    }
}

TIME O(N)SPACE O(H)JAVA · TRAINING PACE · 26 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED