Bug Report for delete-node-in-a-bst #4664
Description
Bug Report for https://neetcode.io/problems/delete-node-in-a-bst
I'm pretty sure the problem "Delete Node in a BST" has a faulty test. Test 7 gives the following input
root=[5,3,6,2,4,null,7]
key=5
When you solve the deletion problem by finding the smallest node in the right subtree as the replacement it works fine.
class Solution:
def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
if not root:
return None
if key < root.val:
root.left = self.deleteNode(root.left, key)
elif key > root.val:
root.right = self.deleteNode(root.right, key)
else:
if not root.right:
return root.left
elif not root.left:
return root.right
else:
replacement_node = root.right
while replacement_node and replacement_node.left:
replacement_node = replacement_node.left
root.val = replacement_node.val
root.right = self.deleteNode(root.right, replacement_node.val)
return rootHowever, if you solve the problem with the largest node in the left subtree it fails.
class Solution:
def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
if not root:
return None
if key < root.val:
root.left = self.deleteNode(root.left, key)
elif key > root.val:
root.right = self.deleteNode(root.right, key)
else:
if not root.right:
return root.left
elif not root.left:
return root.right
else:
replacement_node = root.left
while replacement_node and replacement_node.right:
replacement_node = replacement_node.right
root.val = replacement_node.val
root.left = self.deleteNode(root.left, replacement_node.val)
return rootThe output that this code generates is this:
[4,3,6,2,null,null,7]
but the test says it expects this output:
[6,3,7,2,4]
I believe the former output is still a valid BST, and the problem directions say "There can be multiple results after deleting the node, return any one of them."
