An Introduction To Binary Search Trees In Python

Overview

In this blog post, we're delving into the world of Binary Search Trees (BSTs). A binary search tree is a type of binary tree data structure that has an additional constraint: for each node, all nodes in the left subtree are less (or less/equal depending on conventions) than the node, and all nodes in the right subtree are greater. This crucial property of BSTs allows for operations such as search, insertion, and deletion to be performed relatively efficiently.

We will be implementing a simple Binary Search Tree in Python, complete with search, insert, and delete functionalities.

Python Code for a Binary Search Tree

Below is the basic Python implementation for a Node class, which will serve as the fundamental building block of our Binary Search Tree:

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

Each Node in our BST will have a distinct key along with pointers to its left and right child nodes. If a Node does not have a left or right child, the corresponding pointer will be None.

Implementing Insert

The insert operation modifies the tree to contain the given key, following the rules of BSTs. Here is the Python function for the insert operation:

def insert(root, key):
    if root is None:
        return Node(key)
    else:
        if root.key < key:
            root.right = insert(root.right, key)
        else:
            root.left = insert(root.left, key)
    return root

Implementing Search

The search operation will check for the presence of a key in the tree and return True if it is present and False otherwise.

def search(root, key):
    if root is None or root.key == key:
        return root is not None
    elif root.key < key:
        return search(root.right, key)
    else:
        return search(root.left, key)

Implementing Delete

The delete operation is somewhat more complex due to the additional rules that must be followed during deletion to maintain the BST property.

def minValueNode(node):
    current = node
    while(current.left is not None):
        current = current.left
    return current

def delete(root, key):
    if root is None:
        return root
    if key < root.key:
        root.left = delete(root.left, key)
    elif(key > root.key):
        root.right = delete(root.right, key)
    else:
        if root.left is None:
            return root.right
        elif root.right is None:
            return root.left
        temp = minValueNode(root.right)
        root.key = temp.key
        root.right = delete(root.right, temp.key)
    return root

And that's it! You now have a working Binary Search Tree in Python. From here, you can extend this basic BST to implement more complex data structures and algorithms, or optimize it for specific applications. Happy coding!