PYTHON 3 PLEASE FOLLOW INSTRUCTIONS COMPLETE CODE Problem : Complete the functio

Question

PYTHON 3 PLEASE FOLLOW INSTRUCTIONS

COMPLETE CODE

Problem : 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. (The tree is a binary search tree)

CODE:

class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
  
def deleteNode(root, value):
(node, parent) = findNodeAndParent(root, value)

  
def findNodeAndParent(root, target, parent=None):
# DO NOT MODIFY
if root is None:
return (None, None)
  
if root.value == target:
return (root, parent)

if target < root.value:
return findNodeAndParent(root.left, target, root)
  
return findNodeAndParent(root.right, target, root)
  
def findMinAndParent(root):
# DO NOT DELETE OR MODIFY
if root.left is None:
return (root, None)
if root.left.left is None:
return (root.left, root)
return findMinAndParent(root.left)
  

Explanation / Answer

class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def deleteNode(self, value):
(self, parent) = self.findNodeAndParent(value)
if self.value < parent.value:
if self.left is None and self.right is None:#leaf self
parent.left = None
elif self.right is None:#with only left subtree
parent.left = self.left
else:#use min of right as replacement
(nnode,np) = self.right.findMaxAndParent(self.left)
parent.left = nnode
nnode.left = self.left
nnode.right = self.right
if !(np is None):
np.left = None
else:
if self.left is None and self.right is None:
parent.right = None
elif self.right is None:
parent.right = self.left
else:
(nnode,np) = Node.findMinAndParent(self.right)
parent.right = nnode
nnode.left = self.left
nnode.right = self.right
if !(np is None):
np.left = None
def findNodeAndParent(self, target, parent=None):
# DO NOT MODIFY
if self.value == target:
return (self, parent)
if target < self.value:
if self.left is None:
return (None, self)
return Node.findNodeAndParent(self.left, target, self)
if self.right is None:
return (None, self)
return Node.findNodeAndParent(self.right, target, self)
def addValue(self, value):
Node.addNode(self,Node(value))
def addNode(self, nnode):
(_,parent) = Node.findNodeAndParent(self, nnode.value)
if parent == None:
print 'Node already exists at self'
elif nnode.value < parent.value:
parent.left = nnode
else:
parent.right = nnode
def findMinAndParent(self):
# DO NOT DELETE OR MODIFY
if self.left is None:
return (self, None)
if self.left.left is None:
return (self.left, self)
return Node.findMinAndParent(self.left)
def findMaxAndParent(self):
# DO NOT DELETE OR MODIFY
if self.right is None:
return (self, None)
if self.right.right is None:
return (self.right, self)
return Node.findMaxAndParent(self.left)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.