# Binary Search Tree¶

Before attempting to understand my implementation of the BST, be sure to read the chapter in A Common Sense Guide to Data Structures and Algorithms by Jay Wengrow. It explains why we need such a data structure and helps us understand it better.

Tip

I kid you not, the book makes it fun!

Binary Search Tree Implementation in Python
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158``` ```"""Binary Search Tree Implementation in Python""" class BSTException(Exception): """This exception is raised when a particular facet or requirement of a BST is not satisfied.""" class BinarySearchTreeNode: """A Single node of a Binary Search Tree""" def __init__(self, value, left=None, right=None): self.value = value if left is not None: if left > self.value: raise BSTException( "The left value should be lesser than the current value.") self.left = left if right is not None: if right < self.value: raise BSTException( "The right value should be greater than the current value.") self.right = right def __eq__(self, other): return self.value == other.value def __lt__(self, other): return self.value < other.value def __le__(self, other): return self.value <= other.value def __gt__(self, other): return self.value > other.value def __ge__(self, other): return self.value >= other.value def construct_binary_search_tree(*args): """Given a list of integers, this can construct a BST and returns the root node.""" if len(args) == 0: return elif len(args) > 0: root_node = BinarySearchTreeNode(args) if len(args) > 1: for value in args: insert_into_bst(value, root_node) return root_node def search_bst(search_value, node): """Finds a value in a BST given a node To find a node in a BST, remember: 1. Each node has a maximum of 2 children (a left and a right). 2. The left side of a node has values lesser than the node. 3. The right side of a node has values greater than the node. """ if node is None or node.value == search_value: return node elif search_value < node: return search_bst(search_value, node.left) else: return search_bst(search_value, node.right) def insert_into_bst(value, node): """Inserts a value into a Binary Search Tree 1. If the value to be inserted is less than the current node, it belongs on the left. 2. If the value to be inserted is greater than the current node, it belongs on the right. Remember, all nodes have only a maximum of 2 children: a left child and a right child. """ if value < node: if node.left is None: node.left = BinarySearchTreeNode(value) else: insert_into_bst(value, node.left) elif value > node: if node.right is None: node.right = BinarySearchTreeNode(value) else: insert_into_bst(value, node.right) def delete_from_bst(value, node): """Deletes a value from a BST When deleting remember the following: 1. If the node being deleted has no children, then simply delete it. 2. If the node being deleted has one child, delete the node and plug the child into the spot where the deleted node was. 3. When deleting a node with two children, replace the deleted node with the successor node. The successor node is the child node whose value is the least of all values that are greater than the deleted node. 4. To find the successor node: visit the right child of the deleted value, and then keep on visiting the left child of each subsequent child until there are no more left children. The bottom value is the successor node. 5. If the successor node has a right child, after plugging the successor node into the spot of the deleted node, take the former right child of the successor node and turn it into the left child of the former parent of the successor node. """ if node is None: return None elif value < node: node.left = delete_from_bst(value, node.left) return node elif value > node: if node.left is None: return node.right elif node.right is None: return node.left else: node.right = lift_node_in_bst(node.right, node) return node def lift_node_in_bst(node, node_to_delete): """If the current node of this function has a left child, recursively call this function to continue down the left subtree to find the successor node. """ if node.left is not None: node.left = lift_node_in_bst(node.left, node_to_delete) return node else: node_to_delete.value = node.value return node.right def traverse_bst_and_run_function(node, function, mode="in-order"): """Traverses a bst and runs a function on each value. The modes are 'in-order', 'pre-order', 'post-order' TODO: Try to implement *returning* the values accrued by these function calls. """ if node is None: return if mode == "in-order": traverse_bst_and_run_function(node.left, function) function(node) traverse_bst_and_run_function(node.right, function) elif mode == "pre-order": function(node) traverse_bst_and_run_function(node.left, function) traverse_bst_and_run_function(node.right, function) elif mode == "post-order": traverse_bst_and_run_function(node.left, function) traverse_bst_and_run_function(node.right, function) function(node) ```