Delete Node in BST LeetCode 450 Guide

LeetCode 450 — Delete Node in a BST gives you the root of a binary search tree and an integer key. Your task is to delete the node with value equal to key from the BST and return the root of the (possibly modified) tree. The BST property must be maintained after deletion.

The key insight is that deletion in a BST is harder than search or insertion because removing a node can disrupt the tree structure. When a leaf node is removed, nothing else needs to change. But when an internal node is removed, its children need to be reattached to the tree in a way that preserves BST ordering.

The problem guarantees that if the key exists in the tree, it appears exactly once (BST values are unique). If the key does not exist, return the root unchanged. The return value is always the root of the modified tree — which may change if the root itself is the node being deleted.

BST deletion has exactly three cases based on the number of children the target node has. Case 1: the node is a leaf (no children) — simply remove it by returning null to the parent. Case 2: the node has exactly one child — remove the node and promote that child to take its place by returning it to the parent. Case 3: the node has two children — this is the tricky case.

For Case 3 (two children), we cannot simply remove the node without disrupting the tree structure. The standard approach is to find the inorder successor — the smallest node in the right subtree — copy its value into the target node, then recursively delete the successor from the right subtree. The successor is guaranteed to have at most one child (no left child), making its own deletion a Case 1 or Case 2.

All three cases are handled recursively. First, we search for the target node using BST ordering (go left if key < node.val, right if key > node.val). Once found, we apply the appropriate case. The recursive structure means we never need to track parent pointers — the call stack handles relinking automatically.

The inorder successor of a node is the next node in the BST's inorder traversal — which visits nodes in ascending sorted order. For a node with a right subtree, the inorder successor is always the leftmost (smallest) node in that right subtree. We find it by going right once, then going left until we reach a node with no left child.

The inorder successor has at most one child — specifically, it may have a right child but never has a left child (if it had a left child, that left child would be the leftmost, not the successor itself). This property is what makes the Case 3 deletion manageable: after copying the successor's value, deleting the successor is a Case 1 or Case 2 deletion.

A helper function to find the minimum node in a subtree is all we need: start at the subtree root, traverse left until node.left is null, return that node. This runs in O(h) time where h is the height of the subtree. In the worst case (right-skewed tree), this is O(n).

The inorder successor is the smallest value in the right subtree, which means it is the smallest value that is still larger than the deleted node. Replacing the deleted node with the successor maintains BST ordering: all left descendants remain smaller than the new value, and all right descendants remain larger.

Formally: if the deleted node has value v, all left subtree nodes have values < v, and the successor has value s where s is the minimum of the right subtree. Since s > v and s is minimal in the right subtree, all other right subtree nodes have values > s. So after replacement: left < s < remaining right — BST property is preserved.

The recursive deletion of the successor from the right subtree also preserves BST property, because it is itself a BST deletion — we trust the recursive call to handle it correctly. This is the core of the recursive correctness argument: if deleteNode correctly handles smaller trees, it correctly handles the full tree.

BST [5,3,6,2,4,null,7], delete key=3. Node 3 has two children: left child 2 and right child 4. This is Case 3. Find the inorder successor: go right to node 4, then go left — node 4 has no left child, so the inorder successor is 4.

Replace node 3's value with the successor's value: node 3 becomes node 4. Now recursively delete value 4 from the right subtree (which was rooted at the original node 4). Node 4 is now a leaf (Case 1), so return null. The right child of what was node 3 is now null.

Result: the tree is [5,4,6,2,null,null,7]. The former node 3 now holds value 4, its left child is 2 (unchanged), its right child is null (the former node 4 was deleted). BST property is maintained: 2 < 4 < 5 < 6 < 7.

Python recursive: def deleteNode(root, key): if not root: return None; if key < root.val: root.left = deleteNode(root.left, key); elif key > root.val: root.right = deleteNode(root.right, key); else: if not root.left: return root.right; if not root.right: return root.left; successor = getMin(root.right); root.val = successor.val; root.right = deleteNode(root.right, successor.val); return root. Helper: def getMin(node): while node.left: node = node.left; return node.

Java recursive follows the same structure with explicit null checks. Time complexity: O(h) for search + O(h) for successor search = O(h) total. Space complexity: O(h) for the recursive call stack. In a balanced BST, h = O(log n), giving O(log n) time and space. In a skewed BST, h = O(n), giving O(n) worst case.

An iterative solution is possible but significantly more complex — it requires tracking parent pointers and handling the three cases with explicit pointer manipulation. The recursive solution is preferred for clarity and correctness, as the call stack naturally handles the parent relinking.

Delete Node in BST is part of the BST CRUD family: Search (LeetCode 700), Insert (LeetCode 701), Delete (LeetCode 450), and Validate (LeetCode 98). Mastering all four gives you the full toolkit for BST manipulation. Search is the foundation — delete uses the same recursive navigation to find the target before handling the three cases.

Lowest Common Ancestor of a BST (LeetCode 235) also uses BST ordering to navigate the tree — it leverages the fact that if both targets are less than the current node you go left, if both are greater you go right, otherwise the current node is the LCA. The same O(h) navigation pattern appears in nearly every BST problem.

Kth Smallest Element in a BST (LeetCode 230) uses inorder traversal — the same inorder successor concept that appears in the two-children deletion case. Understanding inorder traversal order (which yields BST values in ascending sorted order) is fundamental to both the kth-smallest problem and to understanding why the inorder successor is the correct replacement node in BST deletion.