BST Delete

Problem

Delete a key from a binary search tree and return the preorder traversal of the result.

Insert values in order (duplicates ignored). The delete handles all cases: a leaf is removed directly, a node with one child is replaced by that child, and a node with two children is replaced by its inorder successor before that successor is deleted from the right subtree. If the key is absent the tree is unchanged.

Return the preorder values (node, then left, then right).

Hint

For two children, copy the inorder successor's value up and then delete that successor.

Test cases

case 1

in: [[5,3,8,1,4,7,9],3]

expected: [5,4,1,8,7,9]

case 2

in: [[5,3,8],8]

expected: [5,3]

case 3

in: [[5,3,8],3]

expected: [5,8]

case 4

in: [[5,3,8,4],3]

expected: [5,4,8]

case 5

in: [[10,5,15],20]

expected: [10,5,15]

Starter codePython

def bst_delete(values, key):
    # Your code here
    pass

5 test cases · run your code against them in the editor