Class for BST
| 16 | |
| 17 | |
| 18 | class BinarySearchTree: |
| 19 | """Class for BST""" |
| 20 | |
| 21 | def __init__(self): |
| 22 | """Initialising a BST""" |
| 23 | self.root = None |
| 24 | |
| 25 | def insert(self, val): |
| 26 | """Creating a BST with root value as val""" |
| 27 | # Check if tree has root with None value |
| 28 | if self.root is None: |
| 29 | self.root = Node(val) |
| 30 | # Here the tree already has one root |
| 31 | else: |
| 32 | current = self.root |
| 33 | while True: |
| 34 | if val < current.info: |
| 35 | if current.left: |
| 36 | current = current.left |
| 37 | else: |
| 38 | current.left = Node(val) |
| 39 | break |
| 40 | elif val > current.info: |
| 41 | if current.right: |
| 42 | current = current.right |
| 43 | else: |
| 44 | current.right = Node(val) |
| 45 | break |
| 46 | else: |
| 47 | break |
| 48 | |
| 49 | def search(self, val, to_delete=False): |
| 50 | current = self.root |
| 51 | prev = -1 |
| 52 | while current: |
| 53 | if val < current.info: |
| 54 | prev = current |
| 55 | current = current.left |
| 56 | elif val > current.info: |
| 57 | prev = current |
| 58 | current = current.right |
| 59 | elif current.info == val: |
| 60 | if not to_delete: |
| 61 | return "Match Found" |
| 62 | return prev |
| 63 | else: |
| 64 | break |
| 65 | if not to_delete: |
| 66 | return "Not Found" |
| 67 | |
| 68 | # Method to delete a tree-node if it exists, else error message will be returned. |
| 69 | def delete(self, val): |
| 70 | prev = self.search(val, True) |
| 71 | # Check if node exists |
| 72 | if prev is not None: |
| 73 | # Check if node is the Root node |
| 74 | if prev == -1: |
| 75 | temp = self.root.left |