Delete a Node From a Search Tree

Given the root of a binary search tree and an integer `key`, delete the node whose value equals `key` if it exists. Return the possibly new root while preserving the binary search tree property. A binary search tree has this property: for every node, all values in its left subtree are smaller than the node value, and all values in its right subtree are larger. Example: ```text Input: 5 / \ 3 6 / \ \ 2 4 7 key = 3 One valid output: 5 / \ 4 6 / \ 2 7 ``` ### Constraints & Assumptions - Values are unique unless the interviewer states a duplicate policy. - Return the original root if `key` is not found. - The node to delete may be a leaf, have one child, have two children, or be the root. - An iterative or recursive solution is acceptable. - Aim for `O(h)` time where `h` is the tree height. ### Clarifying Questions to Ask - Are duplicate values possible, and if so where are duplicates stored? - May any valid resulting BST shape be returned for the two-child case? - Is the tree balanced, or can it be skewed? - Should the function mutate the existing tree or build a new tree? ### What a Strong Answer Covers - Correct identification of the requested key without disturbing unrelated values. - Correct handling of missing key. - Leaf deletion. - Correct handling of a node with one child. - Correct handling of a node with two children while preserving strict ordering. - Correct root replacement. - Time and space complexity. ### Follow-up Questions - How would the complexity change for a balanced BST versus a skewed BST? - How would you write the solution iteratively? - How would you handle duplicate keys? - How would deletion work in a self-balancing tree such as AVL or Red-Black tree? ### Bounded Root-Reference Variant Implement `Solution.deleteNode(root, key)`. Nodes have `val`, `left`, and `right`; an absent child or empty root is `None` in Python. The tree is a valid BST with unique values. It contains `0` to `10000` nodes, and both node values and `key` are between `-100000` and `100000`, inclusive. Return a root reference, which may be different from the input root. Mutating the supplied tree is permitted for this written implementation. Any resulting BST containing exactly the original values except the deleted key is valid; if the key is absent, return the original root. The original example's two-child deletion also permits this result: ```text 5 / \ 2 6 \ \ 4 7 ``` In level-order notation, the input is `[5,3,6,2,4,null,7]`. Both `[5,4,6,2,null,null,7]` and `[5,2,6,null,4,null,7]` are valid after deleting `3`. Deleting `0` leaves the original tree unchanged. For an empty tree and `key = 0`, return the empty root. ### Existing Console Format The existing console takes `solution(values, key)`, where `values` gives BST insertion order, and returns the resulting inorder value list. This is a separate input/output adapter: the written root-reference task returns a tree, not that list. For insertion order `[5,3,6,2,4,7]` and key `3`, either valid tree above has inorder output `[2,4,5,6,7]`. Level-order arrays with `null` markers are tree illustrations, not insertion-order console inputs. The exposed console statement does not specify a duplicate insertion policy; resolve that policy before extending beyond the unique-value task.