Implementing a Binary Search Tree in Python - Data Structures and Algorithms (DSA) Guide

Introduction

A Binary Search Tree (BST) is a tree-based data structure that has the following properties:

Each node has a unique key.
The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.

In this blog post, we’ll dive deep into implementing a Binary Search Tree in Python.

Structure of a Binary Search Tree

A simple Binary Search Tree can be visually depicted like this:

        15
       /  \
      10   20
     / \   / \
    5  12 18  25

Here, 15 is the root node, and every node in its left subtree, like 10, 5, and 12, is smaller than 15. Every node in its right subtree, such as 20, 18, and 25, is greater than 15.

Python Implementation

Let’s implement a basic Binary Search Tree in Python.

The Node Class

Firstly, we’ll start by creating a Node class to represent each node in the BST.

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

The BinarySearchTree Class

Now we will implement the BinarySearchTree class, which will encapsulate the behaviors of our tree.

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

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

    def delete(self, root, key):
        # Base case: the key is not found in the tree
        if root is None:
            return root

        # Recursive case: traverse the tree to find the node to be deleted
        if key < root.val:
            root.left = self.delete(root.left, key)
        elif key > root.val:
            root.right = self.delete(root.right, key)
        else:  # root.val == key, this is the node to be deleted
            # Node with only one child or no child
            if root.left is None:
                temp = root.right
                root = None
                return temp
            elif root.right is None:
                temp = root.left
                root = None
                return temp

            # Node with two children, find the inorder successor
            root.val = self.minValueNode(root.right).val

            # Delete the inorder successor
            root.right = self.delete(root.right, root.val)

        return root

    def minValueNode(self, root):
        current = root
        while current.left is not None:
            current = current.left
        return current

    def search(self, root, key):
        if root is None or root.val == key:
            return root
        if key < root.val:
            return self.search(root.left, key)
        return self.search(root.right, key)

    def inorder_traversal(self, root):
        if root:
            self.inorder_traversal(root.left)
            print(root.val, end=" ")
            self.inorder_traversal(root.right)

Method Details:

insert: Adds a new node with a given key to the tree.
delete: Removes a node with a given key from the tree and returns the new root.
minValueNode: Helper function to find the node with the smallest value greater than the given node.
search: Searches for a node with a given key in the tree.
inorder_traversal: In-order traversal of the tree, which prints the tree nodes in sorted order.

Deleting a node in a Binary Search Tree (BST) is a bit more complex than inserting or searching for a node. There are three main scenarios to consider when deleting a node:

Leaf Node: The node to be deleted is a leaf node. Simply remove it from the tree.
One Child: The node to be deleted has one child. Remove the node and link its parent to its child.
Two Children: The node to be deleted has two children. Find the inorder successor (the smallest node in its right subtree) and replace the node with it. Then, delete the inorder successor.

Putting It All Together

Let’s use the above code to create a Binary Search Tree.

# Create a new Binary Search Tree
bst = BinarySearchTree()
root = None

# Insert elements
root = bst.insert(root, 15)
bst.insert(root, 10)
bst.insert(root, 20)
bst.insert(root, 5)
bst.insert(root, 12)
bst.insert(root, 18)
bst.insert(root, 25)

# Search for an element
print("Is 18 present?", bool(bst.search(root, 18)))  # Output will be True

# In-order traversal
print("In-order Traversal:")
bst.inorder_traversal(root)  # Output will be 5 10 12 15 18 20 25

# Delete an element
root = bst.delete(root, 10)

# In-order traversal
print("In-order Traversal after deletion:")
bst.inorder_traversal(root)  # Output should be: 5 12 15 18 20 25

If you find this guide useful, please share with others, and spread the knowledge!