The problem
Delete key from a binary search tree and return the root, which may change. If the key is not there, change nothing. Use the method from lesson 5, so that the tests can check the exact shape:
- A node with no children is removed.
- A node with one child is replaced by that child.
- A node with two children takes the key of its successor, the smallest key in its right subtree. Then the successor’s old node is removed (it has at most one child, a right one).
tree from keys 8, 3, 10, 1, 6, 14, 4, 7, 13
delete 3 -> 4 takes 3's place; 6 keeps only its child 7
The tests write a tree as a level-order list: the values level by level, left to right, with None where a child is missing. So [3, 9, 20, None, None, 15, 7] is 3 with children 9 and 20, where 20 has children 15 and 7. An empty tree is None.
Limits
- Up to 100,000 nodes, at most about 50 levels deep; up to 20,000 deletes in a row.
Builds on TREE-4 BST search and insert and TREE-5 Successor and deletion.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | A leaf | Not run | |
| 2 | One child | Not run | |
| 3 | Two children | Not run | |
| 4 | The root | Not run | |
| 5 | Missing key | Not run | |
| 6 | Only node | Not run | |
| 7 | Empty tree | Not run | |
| 8 | Many deletes | Not run | |
| 9 | 100,000 nodes, 20,000 deletes | Not run |