125. Delete a Node From a Binary Search Tree

Given a binary search tree and a value to delete, delete the node with that value (it is guaranteed to exist) and print the inorder traversal of the resulting tree, space-separated. If the tree becomes empty, print 'EMPTY'. The tree is given as space-separated level-order tokens, where 'N' means no node there: the first token is the root, then for each node dequeued in level order you read its left-child token then its right-child token (if input runs out early, remaining children are treated as N). The value to delete is given on the next line.

Input: The first line contains space-separated level-order tokens ('N' for missing children) describing the BST. The second line contains a single integer - the value to delete (guaranteed to exist). Output: Print the inorder traversal of the tree after deletion, space-separated on one line; if the tree becomes empty, print 'EMPTY'.

1 <= number of nodes <= 10^5

Using the successor (smallest in the right subtree) is a CHOICE, not a requirement - using the PREDECESSOR (largest in the left subtree) instead works equally well and is an equally valid alternative, worth mentioning if asked about other approaches.

Remove a specific value from a BST while keeping it a valid BST afterward. Brute force: Collect ALL values via inorder traversal, remove the target value from that list, then rebuild an entirely new balanced BST from the remaining sorted values - this works but discards the tree's original shape and structure entirely, doing far more work than a targeted, localized deletion. Optimised: Handling the deletion directly within the existing tree structure (leaf removal, single-child replacement, or successor-swap-and-recurse for two children) modifies only the small localized region around the deleted node, preserving the rest of the tree's structure untouched - far more efficient than rebuilding from scratch.

Do an inorder traversal of the tree to get all values in sorted order, remove the target value from that array, and then build a brand-new BST from scratch by inserting the remaining values one at a time using standard BST insertion. This is correct because deleting a value and keeping the BST property is equivalent to rebuilding a BST over the remaining sorted values, but repeatedly inserting into a fresh tree can degrade to a skewed shape and costs quadratic time in the worst case, plus it throws away the original tree structure entirely. Time: O(n^2) worst case Space: O(n)

Perform the exact same successor-replacement deletion logic, but iteratively: walk down the tree with a parent pointer to locate the node to delete, and if it has two children, walk down again to find the inorder successor and its parent, then relink pointers directly instead of recursing. This gives identical results to the recursive version but uses only O(1) auxiliary space instead of an O(h) call stack, which matters here since n can be up to 10^5 and a skewed tree could otherwise risk deep recursion. Time: O(h) (O(log n) balanced, O(n) worst case skewed) Space: O(1)

Recursively search for the node to delete by comparing against the target at each step. If it's a leaf or has one child, splice it out directly; if it has two children, find its inorder successor (the leftmost node in its right subtree), copy that value into the node being deleted, and recursively delete the successor node from the right subtree instead. This preserves the BST property in place without rebuilding anything, touching only the path from the root down to the deleted node. Time: O(h) (O(log n) balanced, O(n) worst case skewed) Space: O(h) recursion stack

1. Find the node with the target value using standard BST search. 2. If it's a LEAF, simply remove it directly - nothing else needs to change. 3. If it has only ONE child, replace it directly with that child. 4. If it has TWO children, replace its value with its INORDER SUCCESSOR (the smallest value in its right subtree), then recursively delete that successor node instead (which is guaranteed to have at most one child, reducing to an easier case).

Time: O(h), where h is the tree's height - finding the node, then handling its specific deletion case, are both bounded by the tree's height. Space: O(h) for the recursion stack.

Test deleting the only node of a single-node tree ('EMPTY'), deleting a leaf, deleting a node with exactly one child, and deleting a node with two children (requires its inorder successor).

Be ready to walk through all THREE deletion cases clearly (leaf, one child, two children) - this is one of the most commonly asked BST operations precisely because it requires careful case analysis, unlike simpler BST search or insertion.