What is a Binary Search Tree and how to write a binary search tree in Python

A binary search tree (BST) is a data structure that allows for fast insertion, deletion, and search operations. It is called a “binary” tree because each node has at most two children. The left child of a node is always less than the node’s value, and the right child is always greater.

One advantage of a BST is that it can be easily implemented in Python using just a few basic data structures. In this article, we will go over how to write a BST in Python and provide some examples of how it can be used.

To start, let’s define the structure of a BST node. Each node will have a value and pointers to its left and right children:

class BSTNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

Next, we will define the BST itself. We will keep track of the root node and will define methods for inserting, deleting, and searching for values in the tree:

class BST:
    def __init__(self):
        self.root = None

    def insert(self, value):
        # code for inserting a value into the tree goes here

    def delete(self, value):
        # code for deleting a value from the tree goes here

    def search(self, value):
        # code for searching for a value in the tree goes here

Now, let’s go over how to implement the insert, delete, and search methods.

Inserting a Value

To insert a value into a BST, we first need to check if the tree is empty. If it is, we can simply set the root node to a new BSTNode with the value we want to insert. If the tree is not empty, we need to find the correct place to insert the new node.

To do this, we will start at the root node and compare the value we want to insert to the value of the current node. If the value is less than the current node’s value, we will move to the left child. If the value is greater, we will move to the right child. We continue this process until we reach a leaf node (a node with no children). At this point, we can insert the new node as the left or right child of the leaf node, depending on whether the value is less than or greater than the leaf node’s value.

Here is the code for the insert method:

def insert(self, value):
    new_node = BSTNode(value)
    if self.root is None:
        self.root = new_node
        return
    current_node = self.root
    while True:
        if value < current_node.value:
            if current_node.left is None:
                current_node.left = new_node
                return
            current_node = current_node.left
        else:
            if current_node.right is None:
                current_node.right = new_node
                return
            current_node = current_node.right

Deleting a Value

Deleting a value from a BST is a bit more complicated than inserting a value. There are three cases we need to consider:

1. The node we want to delete is a leaf node (has no children). In this case, we can simply remove the node from the tree.
2. The node we want to delete has one child. In this case, we can simply replace the node with its child. 3. The node we want to delete has two children. In this case, we need to find the smallest value in the right subtree of the node and use that value to replace the node. Then, we can delete the smallest value from the right subtree.
3. Here is the code for the delete method:

def delete(self, value):
    if self.root is None:
        return
    current_node = self.root
    parent = None
    while current_node is not None and current_node.value != value:
        parent = current_node
        if value < current_node.value:
            current_node = current_node.left
        else:
            current_node = current_node.right
    if current_node is None:
        return
    # Case 1: Leaf node
    if current_node.left is None and current_node.right is None:
        if parent is None:
            self.root = None
        elif parent.left == current_node:
            parent.left = None
        else:
            parent.right = None
    # Case 2: Node with one child
    elif current_node.left is None:
        if parent is None:
            self.root = current_node.right
        elif parent.left == current_node:
            parent.left = current_node.right
        else:
            parent.right = current_node.right
    elif current_node.right is None:
        if parent is None:
            self.root = current_node.left
        elif parent.left == current_node:
            parent.left = current_node.left
        else:
            parent.right = current_node.left
    # Case 3: Node with two children
    else:
        successor = current_node.right
        while successor.left is not None:
            successor = successor.left
        current_node.value = successor.value
        self.delete(successor.value)

Searching for a Value

To search for a value in a BST, we simply need to start at the root node and compare the value we are searching for to the value of the current node. If the value is less than the current node’s value, we move to the left child. If the value is greater, we move to the right child. We continue this process until we either find the value or reach a leaf node without finding the value.

Here is the code for the search method:

def search(self, value):
    current_node = self.root
    while current_node is not None and current_node.value != value:
        if value < current_node.value:
            current_node = current_node.left
        else:
            current_node = current_node.right
    return current_node is not None

Example

Here is an example of how to use our BST class to create a tree and perform some basic operations:

# Create a new BST
tree = BST()

# Insert some values into the tree
tree.insert(5)
tree.insert(3)
tree.insert(8)
tree.insert(1)
tree.insert(4)
tree.insert(7)
tree.insert(10)

# Search for a value in the tree
print(tree.search(4))  # True
print(tree.search(6))  # False

# Delete a value from the tree
tree.delete(8)
print(tree.search(8))  # False

Conclusion

In this article, we went over how to write a binary search tree in Python. We defined the BSTNode class to represent a single node in the tree and the BST class to represent the tree itself. We also implemented methods for inserting, deleting, and searching for values in the tree. With these basic building blocks, you can use a BST to efficiently store and manipulate data in your Python programs.