| 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 |
| 76 | prev2 = None |
| 77 | while temp.right: |
| 78 | prev2 = temp |
| 79 | temp = temp.right |
| 80 | if prev2 is None: |
| 81 | self.root.left = temp.left |
| 82 | self.root.info = temp.info |
| 83 | else: |
| 84 | prev2.right = None |
| 85 | self.root.info = temp.info |
| 86 | print("Deleted Root ", val) |
| 87 | # Check if node is to left of its parent |
| 88 | elif prev.left and prev.left.info == val: |
| 89 | # Check if node is leaf node |
| 90 | if prev.left.left is prev.left.right: |
| 91 | prev.left = None |
| 92 | print("Deleted Node ", val) |
| 93 | # Check if node has child at left and None at right |
| 94 | elif prev.left.left and prev.left.right is None: |
| 95 | prev.left = prev.left.left |
| 96 | print("Deleted Node ", val) |
| 97 | # Check if node has child at right and None at left |
| 98 | elif prev.left.left is None and prev.left.right: |
| 99 | prev.left = prev.left.right |
| 100 | print("Deleted Node ", val) |
| 101 | # Here node to be deleted has 2 children |
| 102 | elif prev.left.left and prev.left.right: |
| 103 | temp = prev.left |
| 104 | while temp.right is not None: |
| 105 | prev2 = temp |
| 106 | temp = temp.right |
| 107 | prev2.right = None |
| 108 | prev.left.info = temp.info |
| 109 | print("Deleted Node ", val) |
| 110 | else: |
| 111 | print("Error Left") |
| 112 | |
| 113 | # Check if node is to right of its parent |
| 114 | elif prev.right.info == val: |
| 115 | flag = 0 |
| 116 | # Check is node is a leaf node |
| 117 | if prev.right.left is prev.right.right: |
| 118 | prev.right = None |
| 119 | flag = 1 |
| 120 | print("Deleted Node ", val) |
| 121 | # Check if node has left child at None at right |
| 122 | if prev.right and prev.right.left and prev.right.right is None: |
| 123 | prev.right = prev.right.left |
| 124 | print("Deleted Node ", val) |
| 125 | # Check if node has right child at None at left |
| 126 | elif prev.right and prev.right.left is None and prev.right.right: |