Write a program in PYTHON for creating a binary search tree (BST) from a given n

Question

Write a program in PYTHON for creating a binary search tree (BST) from a given number randomly generated (distinct) integer values in a given interval [i, j], such that the height of the resulting BST is the lowest. Your program should take as input three integers –the number of values (n), and the bounds i and j. Inside the program, n distinct integers, each in the interval [i, j], will be created (by repeated calls to the random number generator), and then these n integers will be stored in a lowest-height BST; finally the integers stored in the BST will be printed (by inorder traversal of the tree). Show your program’s input and output for two different sets of input values (e.g., first run inputs: n=10, i=1, j=50; second run inputs: n=15, i = 5, j =100).

Explanation / Answer

def findSuccessor(self): succ = None if self.hasRightChild(): succ = self.rightChild.findMin() else: if self.parent: if self.isLeftChild(): succ = self.parent else: self.parent.rightChild = None succ = self.parent.findSuccessor() self.parent.rightChild = self return succ def findMin(self): current = self while current.hasLeftChild(): current = current.leftChild return current def spliceOut(self): if self.isLeaf(): if self.isLeftChild(): self.parent.leftChild = None else: self.parent.rightChild = None elif self.hasAnyChildren(): if self.hasLeftChild(): if self.isLeftChild(): self.parent.leftChild = self.leftChild else: self.parent.rightChild = self.leftChild self.leftChild.parent = self.parent else: if self.isLeftChild(): self.parent.leftChild = self.rightChild else: self.parent.rightChild = self.rightChild self.rightChild.parent = self.parent

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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