# aaaa

Jul 5th, 2022
965
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. # Your implementation goes here
2.
3. class BinarySearchTree:
4.     # This is a Node class that is internal to the BinarySearchTree class
5.     class __Node:
6.         def __init__(self, val, left=None, right=None):
7.             self.val = val
8.             self.left = left
9.             self.right = right
10.
11.         def getVal(self):
12.             return self.val
13.
14.         def setVal(self, newval):
15.             self.val = newval
16.
17.         def getLeft(self):
18.             return self.left
19.
20.         def getRight(self):
21.             return self.right
22.
23.         def setLeft(self, newleft):
24.             self.left = newleft
25.
26.         def setRight(self, newright):
27.             self.right = newright
28.
29.         # This method deserves a little explanation. It does an inorder traversal
30.         # of the nodes of the tree yielding all the values. In this way, we get
31.         # the values in ascending order.
32.         def __iter__(self):
33.             if self.left != None:
34.                 for elem in self.left:
35.                     yield elem
36.             yield self.val
37.             if self.right != None:
38.                 for elem in self.right:
39.                     yield elem
40.
41.     # Below methods of the BinarySearchTree class.
42.     def __init__(self):
43.         self.root = None
44.
45.     def insert(self, val):
46.         # The __insert function is recursive and is not a passed a self parameter.
47.         # It is a # static function (not a method of the class) but is hidden inside the insert
48.         # function so users of the class will not know it exists.
49.         def __insert(root, val):
50.             if root == None:
51.                 return BinarySearchTree.__Node(val)
52.             if val < root.getVal():
53.                 root.setLeft( __insert(root.getLeft(), val) )
54.             else:
55.                 root.setRight(__insert(root.getRight(), val))
56.             return root
57.
58.         self.root = __insert(self.root, val)
59.
60.     def search(self, val):
61.         def __search(root,val):
62.             if root == None:
63.                 return False
64.             if root.getVal() == val:
65.                 return True
66.             if val < root.getVal():
67.                 return __search(root.getLeft(), val)
68.             return __search(root.getRight(), val)
69.
70.         return __search(self.root,val)