#starter_code

class BTNode: '''Binary Tree Node class - do not modify''' def __init__(self, value, left, right): '''Stores a reference to the value, left child node, and right child node. If no left or right child, attributes should be None.''' self.value = value self.left = left self.right = right

class BST: def __init__(self): # reference to root node - do not modify self.root = None

def insert(self, value): '''Takes a numeric value as argument. Inserts value into tree, maintaining correct ordering. Returns nothing.''' pass

def search(self, value): '''Takes a numeric value as argument. Returns True if its in the tree, false otherwise.''' pass

def height(self): '''Returns the height of the tree. A tree with 0 or 1 nodes has a height of 0.''' pass

def preorder(self): '''Returns a list of the values in the tree, in pre-order order.''' pass

Implement a binary search tree. Requirements: Your code must be in a class named BST. You must implement these four methods: insert, search, preorder, and height. All of these methods must be implemented recursively. You may write recursive helper functions if needed. Your binary search tree must be implemented using the BTNode class provided in the starter code. If a node doesn't have a left and/or right child, the left and/or right attributes should be None. You may not use any other data structures to store your tree nodes. Your BST class should store a reference to the root node in an attribute called root. .insert will take a numeric value as an argument and insert it into the tree, maintaining the binary search tree's ordering. It should return nothing, If the value is already in the tree, it should not be re-inserted; the tree should contain no duplicate values. search will take a numeric value as an argument and return True if the value is in the tree and False otherwise, preorder will perform a pre-order tree traversal, returning a list of the tree's values in pre-order order. height will return the height of the tree. A tree with zero or one nodes has a height of O. Here's an example of how your BST should work: bat RST) for value in [4, 2, 5, 3, 1, 6, 71: bat.. inaert. (value) # BST ow looks like this: + 1 1 # 2 5 + A 1 prinLbs.search (5)) | True print (bst.search (8) False print (bst.preorder()) # L', 2, 1, 3, 5, 6, 7] print (bot.height ()) ! 3