Binary search trees (BSTs) are a sort of data structure that is used to store and search for data effectively. A BST is a tree structure with no more than two children: a left child and a right child. The left child is always smaller than the parent node, whereas the right child is always greater than the parent node. The most significant feature of a BST is that it enables efficient searching. This is due to the BST's recursive nature, which enables binary search methods to be implemented. We shall look at the explanation of a BST and its insert, lookup and remove methods in Python
Binary Search Trees are made up of nodes and edges. The nodes are the various points in the memory that holds the data. In the diagram below, the colored circles are the nodes and the black lines connecting them are the edges.
The root node of a BST is the first node. It is called root because all other nodes in the BST originate from this root node. In the example above, node 101 is the root node.
In a BST, the leaf nodes are nodes that do not have either a left child or a right child. They are the last node in the tree and they are of great importance in a BST. From the example above, nodes 9, 37, 54 and node 144 are leaf nodes.
Parent nodes in a BST are nodes that have either a left child or right child or even both children. In the example above, node 33 is the parent node of nodes 9 and 7, and node 105 is the parent node of nodes 54 and 144. The root node is also a parent node and it is the parent node of nodes 33 and 105.
In a BST, there are three main methods which are insert, lookup and remove. These methods are used to insert, find and remove a node respectively. We will now look at how to implement these methods.
Since a BST is made up of different nodes, we need to first define our node class
class Node: def __init__(self, value): self.left = None self.right = None self.value = value def __repr__(self): return str(self.__dict__)
In this code snippet above, the node has a left and right pointer as well as the value it will hold. It also has a 'repr' class that we are implementing to determine how we want to output our node. In this case, we are choosing it to be a python dictionary or an object.
class BinarySearchTree(): def __init__(self) -> None: self.root = None def __repr__(self) -> None: return str(self.__dict__)
Here we are just stating the constructor for the BST class and also implementing our choice of output. By default, the BST object we are creating is going to have a root node.
def insert(self, value): newNode = Node(value) if self.root == None: self.root = newNode return currentNode = self.root while True: if currentNode.value > newNode.value: if currentNode.left == None: currentNode.left = newNode return currentNode = currentNode.left if currentNode.value < newNode.value: if currentNode.right == None: currentNode.right = newNode return currentNode = currentNode.right
We first check if the tree is empty by evaluating the value of the root property. Since we do not know where we are going to end, if the currentnode's value is greater than the newnode's value, we also check if there is an already existing direct child node to the left of the currentnode. If there is no node, we insert the newnode there or we continue to traverse to the leftmost node of the currentnode. We also do the same thing for the right subtree of the node by checking if the currentnode's value is less than the newnode's value. Then we perform the same operation but this time, we will be traversing to the rightmost node.
def lookup(self, value): if self.root == None: print("Empty Tree") return currentNode = self.root while currentNode: if currentNode.value > value: currentNode = currentNode.left elif currentNode.value < value: currentNode = currentNode.right elif currentNode.value == value: print("Found") return currentNode print("Not Found") return None
In this lookup method, we check if the tree is empty, else we continue to look for the node by comparing the value of the currentnode to the value we are looking for. If the currentnode is greater than the value we are looking for, then we going leftward and if the currentnode is smaller than the value, then we are going right.
This is the trickiest and longest method, but we are going to discuss it together. When you want to delete a node from a BST. YOu would be faced with any of the following three scenarios:
- If the node has no children - Just delete it.
- If the node has a single child - Copy that child to the node.
- If the node has two children - Determine the next highest element in the right subtree. Replace the node to be removed with the next highest node. Delete the next node. So we find the leftmost node of the right subtree of the current node. This leftmost node can be found by looping from the current node to the last node (until when there is no left node). This will reduce the problem to a scenario where the node has only one child or no child.
def remove(self, value): if self.root == None: return "Empty List" currentNode = self.root parentNode = None while currentNode != None: if currentNode.value > value: parentNode = currentNode currentNode = currentNode.left elif currentNode.value < value: parentNode = currentNode currentNode = currentNode.right else: # A match has been found # Both left and right children if currentNode.left != None and currentNode.right != None: badNode = currentNode.right badNodeParent = currentNode.right while badNode.left != None: badNodeParent = badNode badNode = badNode.left currentNode.value = badNode.value if badNode == badNodeParent: currentNode.right = badNode.right if badNode.right == None: badNodeParent.left = None return else: badNodeParent.left = badNode.right return # No left or right children elif currentNode.left == None and currentNode.right == None: if parentNode == None: self.root = None return if parentNode.value > currentNode.value: parentNode.left = None return else: parentNode.right = None return # Only left child elif currentNode.left != None and currentNode.right == None: if parentNode == None: self.root = None return if parentNode.value > currentNode.value: parentNode.left = currentNode.left return else: parentNode.right = currentNode.left return # Only right child elif currentNode.left == None and currentNode.right != None: if parentNode == None: self.root = None if parentNode.value > currentNode.value: parentNode.left = currentNode.right return else: parentNode.right = currentNode.right return
The Time Complexity of BST operations is O(h). h is the height of the tree.
The source code for this tutorial can be found at https://github.com/valentinesamuel/EssentialOrigin/blob/main/test_ds/binary_search_tree.py
It is crucial to note, however, that the effectiveness of a BST is dependent on the structure of the tree. The efficiency of operations can be dramatically lowered if the tree is imbalanced (i.e., one subtree is significantly bigger than the other). There are numerous approaches for balancing BSTs, such as AVL trees and red-black trees, to address this issue. These strategies will be detailed in a subsequent post.
Don't forget to leave a like or comment. Till next time guys.