The tree is a search tree with distinct keys: for every node, all keys in its left subtree are smaller than the node's key, and all keys in its right subtree are larger.
TreeNode(val, left=None, right=None) is in the starter. Keep it.
Write remove_key(root, key) -> TreeNode: take key out of the tree and return the root of what's left. So that there is exactly one right answer, follow these rules for the node x holding key:
- If
xhas no left child, its right subtree (possibly empty) takes its place. - Otherwise, if
xhas no right child, its left subtree takes its place. - Otherwise, find the smallest key in
x's right subtree, write that key intox, and remove the node it came from (it has no left child, so rule 1 applies there).
If key isn't in the tree, return the tree unchanged.
# 8 8 8
# / \ / \ / \
# 3 12 4 12 3 15
# / \ \ / \ \ / \
# 1 6 15 1 6 15 1 6
# / \ \ / \
# 4 7 7 4 7
# (the tree) remove_key(t, 3) remove_key(t, 12)
remove_key(t, 99) # t, unchanged
remove_key(TreeNode(5), 5) # None
- Up to 70,000 nodes, at most 500 levels deep. Keys are distinct integers between
-10^9and10^9. - Aim for O(h), where
his the height of the tree. The tests count how many nodes you look at, so don't rebuild the tree.
Show hint
First walk down to the node, remembering its parent. The hard case is a node with two children: the next larger key sits at the far left of its right subtree.