given a root node reference of a bst and a key delete the node with the given key in the bst return the root node reference possibly updated of the bst basically the deletion can be divided into two stages search for a node to remove if the node is found delete the node note time complexity should be oheight of tree example root 5 3 6 2 4 null 7 key 3 5 3 6 2 4 7 given key to delete is 3 so we find the node with value 3 and delete it one valid answer is 5 4 6 2 null null 7 shown in the following bst 5 4 6 2 7 another valid answer is 5 2 6 null 4 null 7 5 2 6 4 7 type root treenode type key int rtype treenode find the right most leaf of the left subtree attach right child to the right of that leaf return left child instead of root a k a delete root if left or right child got deleted the returned root is the child of the deleted node type root treenode type key int rtype treenode find the right most leaf of the left sub tree attach right child to the right of that leaf return left child instead of root a k a delete root if left or right child got deleted the returned root is the child of the deleted node
class Solution(object):
    def delete_node(self, root, key):
        
        if not root: return None

        if root.val == key:
            if root.left:
                
                left_right_most = root.left
                while left_right_most.right:
                    left_right_most = left_right_most.right
                
                left_right_most.right = root.right
                
                return root.left
            else:
                return root.right
        
        elif root.val > key:
            root.left = self.deleteNode(root.left, key)
        else:
            root.right = self.deleteNode(root.right, key)
        return root