What is a binary search tree in Python?

Question

Jayant Kumar · Accepted Answer

Table of Contents
Introduction
A Binary Search Tree (BST) is a fundamental data structure used for efficient searching, inserting, and deleting operations. In Python, a BST is implemented using nodes, each with references to left and right children. The structure and properties of BST make it ideal for searching and sorting applications.
1. Structure and Properties of a Binary Search Tree
Structure
A Binary Search Tree is a type of binary tree where each node has at most two children. The left child’s value is always less than the parent node’s value, and the right child’s value is greater. This property makes searching efficient.
Properties

Binary Property: Each node has up to two children.
Search Property: For any given node N, all values in the left subtree are less than N, and all values in the right subtree are greater than N.
No Duplicates: A typical BST doesn’t contain duplicate elements, though this can vary based on implementation.

2. Operations on a Binary Search Tree
Insertion
Inserting into a BST involves placing the new value in its correct position to maintain the BST property. The value is compared with the root node and recursively inserted into the left or right subtree.
Search
BSTs allow efficient searching because they divide the dataset into two parts at each level. Searching for a value involves traversing the tree based on comparisons (O(log n) in average cases).
Deletion
Deleting a node from a BST can be complex. There are three cases:

The node is a leaf (no children).
The node has one child.
The node has two children (the most complex case, involving replacing the node with the smallest value in the right subtree or the largest in the left subtree).

Practical Examples
Here’s a Python implementation of a Binary Search Tree, including insertion and search operations.
Example 1: Insertion and Search in a Binary Search Tree
class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.value = key

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

# Insert a node into the BST
    def insert(self, key):
        if self.root is None:
            self.root = Node(key)
        else:
            self._insert_recursive(self.root, key)
    
    def _insert_recursive(self, current, key):
        if key &#x3C; current.value:
            if current.left is None:
                current.left = Node(key)
            else:
                self._insert_recursive(current.left, key)
        else:
            if current.right is None:
                current.right = Node(key)
            else:
                self._insert_recursive(current.right, key)

# Search for a value in the BST
    def search(self, key):
        return self._search_recursive(self.root, key)
    
    def _search_recursive(self, current, key):
        if current is None or current.value == key:
            return current
        if key &#x3C; current.value:
            return self._search_recursive(current.left, key)
        return self._search_recursive(current.right, key)

# Example usage
bst = BinarySearchTree()
bst.insert(50)
bst.insert(30)
bst.insert(70)
bst.insert(20)
bst.insert(40)
bst.insert(60)
bst.insert(80)

# Searching for an element
node = bst.search(40)
if node:
    print(f"Node with value {node.value} found.")
else:
    print("Node not found.")

Example 2: Deletion in a Binary Search Tree
class BinarySearchTreeWithDeletion(BinarySearchTree):
    # Deleting a node
    def delete(self, key):
        self.root = self._delete_recursive(self.root, key)
    
    def _delete_recursive(self, current, key):
        if current is None:
            return current
        if key &#x3C; current.value:
            current.left = self._delete_recursive(current.left, key)
        elif key > current.value:
            current.right = self._delete_recursive(current.right, key)
        else:
            # Node with one or no child
            if current.left is None:
                return current.right
            elif current.right is None:
                return current.left
            
            # Node with two children, replace with the smallest in the right subtree
            temp = self._min_value_node(current.right)
            current.value = temp.value
            current.right = self._delete_recursive(current.right, temp.value)
        return current

def _min_value_node(self, node):
        current = node
        while current.left is not None:
            current = current.left
        return current

Conclusion
A Binary Search Tree (BST) is an efficient data structure for searching, inserting, and deleting elements. It is especially useful when working with sorted data. In Python, BST can be implemented using a class-based approach. By maintaining its unique properties, a BST ensures optimized search operations, making it a valuable tool in various applications such as database indexing, file systems, and more.

What is a binary search tree in Python?

Similar Questions