Complete the function deleteNode() to take in a root node of a tree and a value of a node that is in the tree, and delete that node. PYTHON

class Node: def __init__(self, value): self.value = value self.left = None self.right = None def deleteNode(root, value): (node, parent) = findNodeAndParent(root, value) # case #1, if the target node doesn't have any children, remove it # if the target node is root, after deleting it, root will be None # else,if the target node is the left child or right child of it's parent, make # left or right child as none accordingly # case #2, if the node has only one child, # make the child of the target node a direct child of it's parent node # case #3, if the target node has two children # Find the successor and its parent using findSuccessorAndParent() # Replace target node value with successor node value # # Remove the successor by making its right child as # the left child of the successor's parent def findNodeAndParent(root, target, parent=None): # DO NOT DELETE OR MODIFY # this function searches for a node with `value` # and returns the node and its parent if root is None: return (None, None) if root.value == target: return (root, parent) if target < root.value: return findNodeAndParent(root.left, target, root) else: return findNodeAndParent(root.right, target, root) def findSuccessorAndParent(root): # DO NOT DELETE OR MODIFY if root.left and root.right is None: # the starting node is min and we don't have a way to access its parent return (root, None) #There are three cases to consider when looking for the successor:

#If the node has a right child, then the successor is the smallest key in the right subtree. #If the node has no right child and is the left child of its parent, then the parent is the successor. #If the node is the right child of its parent, and itself has no right child, then the successor to this node is the successor of its parent, excluding this node.