root of a binary search tree (all values are distinct; every node's left subtree holds smaller values and its right subtree larger ones) and a number key. Remove the node holding key and return the root of the resulting tree.
The removal must follow exactly this rule:
- if no node holds key, the tree is unchanged;
- if the node has no children or a single child, that child (or nothing) takes its place;
- if it has two children, its right child takes its place, and its whole left subtree is attached as the left child of the smallest node in the right subtree.
Try to do it in time proportional to the height of the tree.root=tree_node([10, 5, 15, 3, 8, None, 20]), key=5 → [10, 8, 15, 3, None, None, 20]
Node 5 has two children. Its right child 8 takes its place, and the left subtree (node 3) is hung as the left child of the smallest node in the right subtree, which is 8 itself.
root=tree_node([10, 5, 15, 3, 8, None, 20]), key=15 → [10, 5, 20, 3, 8]
Node 15 has only a right child, which simply takes its place.
root=tree_node([10, 5, 15]), key=7 → [10, 5, 15]
Key 7 is not in the tree, so the tree stays the same.
root is a valid binary search treeroot=tree_node([10, 5, 15, 3, 8, None, 20]), key=5
[10, 8, 15, 3, None, None, 20]
Run checks the first 3 tests in your browser. Submit checks all 63 tests on the server, hidden ones included.