#450 Delete Node in a BST

Mediumsolve on LeetCode ↗

frequently reported atOracle Uber ByteDance / TikTok Flipkart Amazon Bloomberg

the problem

In plain words

Delete the node with value key (if present) and return the root of the still-valid BST.

in root = [5,3,6,2,4,null,7], key = 3

out [5,4,6,2,null,null,7]

3 has two children; its successor 4 replaces it.

in root = [5,3,6,2,4,null,7], key = 0

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

0 is not in the tree.

in root = [], key = 0

out []

0 ≤ number of nodes ≤ 10⁴
-10⁵ ≤ Node.val, key ≤ 10⁵
Values are unique
Follow-up: O(height)

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternBST property

Deleting a node with two children is hard; deleting a node with ≤ 1 child is easy. So replace the hard case with an easy one: copy in the successor, then delete the successor (it has no left child).

solutions

From brute force to optimal

Inorder into a list, drop the key, rebuild a balanced BST.

Collect values in order.
Remove key.
Build middle-as-root.

timeO(n)

Every node is copied.

spaceO(n)

List plus a new tree.

javajava.util.*

1class Solution {2    /** Flatten to a sorted list, drop the key, rebuild balanced. O(n) no matter where the key is. */3    public TreeNode deleteNode(TreeNode root, int key) {4        List<Integer> values = new ArrayList<>();5        collect(root, values);6        values.remove(Integer.valueOf(key));   // remove the value, not the index7        return build(values, 0, values.size() - 1);8    }9 10    private void collect(TreeNode node, List<Integer> out) {11        if (node == null) return;12        collect(node.left, out);13        out.add(node.val);14        collect(node.right, out);15    }16 17    private TreeNode build(List<Integer> values, int lo, int hi) {18        if (lo > hi) return null;19        int mid = lo + (hi - lo) / 2;20        return new TreeNode(values.get(mid), build(values, lo, mid - 1), build(values, mid + 1, hi));21    }22}

Find the node; handle 0/1 child by returning the other child; with 2 children copy the successor and delete it from the right subtree.

key < root → root.left = delete(left); key > root → root.right = delete(right).
Found, no left child → return right. No right child → return left.
Two children: succ = leftmost of right subtree; root.val = succ.val; root.right = delete(right, succ.val).

timeO(h)

One path to the node plus one path to its successor — both inside one root-to-leaf walk.

spaceO(h)

Recursion stack.

javajava.util.*

1class Solution {2    public TreeNode deleteNode(TreeNode root, int key) {3        if (root == null) return null;                                       // key not found4        if (key < root.val) root.left = deleteNode(root.left, key);5        else if (key > root.val) root.right = deleteNode(root.right, key);6        else {7            // cases 1 & 2: zero or one child → the other side replaces this node8            if (root.left == null) return root.right;9            if (root.right == null) return root.left;10            // case 3: two children → copy the in-order successor, then delete it11            TreeNode succ = root.right;12            while (succ.left != null) succ = succ.left;                      // smallest on the right13            root.val = succ.val;14            root.right = deleteNode(root.right, succ.val);15        }16        return root;17    }18}

sim

Dry run

loading simulation…

javajava.util.*

1class Solution {2    public TreeNode deleteNode(TreeNode root, int key) {3        if (root == null) return null;                                       // key not found4        if (key < root.val) root.left = deleteNode(root.left, key);5        else if (key > root.val) root.right = deleteNode(root.right, key);6        else {7            // cases 1 & 2: zero or one child → the other side replaces this node8            if (root.left == null) return root.right;9            if (root.right == null) return root.left;10            // case 3: two children → copy the in-order successor, then delete it11            TreeNode succ = root.right;12            while (succ.left != null) succ = succ.left;                      // smallest on the right13            root.val = succ.val;14            root.right = deleteNode(root.right, succ.val);15        }16        return root;17    }18}

in the room

How to say it in the interview

talk track

List the three cases out loud before coding.
Explain why the successor works: it's the smallest value larger than the deleted one.
Mention the predecessor as an equally valid choice.

traps

Forgetting to assign the recursive result back to root.left / root.right.
Searching for the successor in the left subtree (that's the predecessor's side — fine, but then take its rightmost node).

what they ask next

Follow-ups

Delete without copying values (nodes carry other data)?

Relink instead: detach the successor from its parent (its right child takes its place), then give it the deleted node's left and right children.

before you submit

Edge cases to test

key isn't in the tree → return the tree unchanged.
Deleting the only node → return null.
The successor is the node's own right child (it has no left subtree) → it moves up one level.

practise next