Binary Search Tree - Insert, Lookup and Remove
Valentine Samuel
Posted on March 13, 2023
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
Basic Concepts
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.
Root Nodes
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.
Leaf Nodes
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
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.
BST Methods
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.
Node Class
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.
Binary Search Tree Class
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.
Insert Method
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.
Lookup Method
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.
Remove method
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
Conclusion
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.
❤️❤️❤️
Posted on March 13, 2023
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.
Related