What is a binary search tree in Python?

Question

Jayant Kumar · Accepted Answer

A binary search tree (BST) is a type of binary tree data structure that follows a specific ordering property. In a binary search tree, each node stores a key (or value), and the left subtree of a node contains keys that are smaller than the node's key, while the right subtree contains keys that are greater than the node's key. This ordering property allows for efficient searching, insertion, and deletion operations.
Here's an example implementation of a binary search tree in Python:
class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

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

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.key:
            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)

def search(self, key):
        return self._search_recursive(self.root, key)

def _search_recursive(self, current, key):
        if current is None or current.key == key:
            return current
        if key &#x3C; current.key:
            return self._search_recursive(current.left, key)
        else:
            return self._search_recursive(current.right, key)

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.key:
            current.left = self._delete_recursive(current.left, key)
        elif key > current.key:
            current.right = self._delete_recursive(current.right, key)
        else:
            if current.left is None:
                return current.right
            elif current.right is None:
                return current.left
            else:
                min_key = self._find_min_key(current.right)
                current.key = min_key
                current.right = self._delete_recursive(current.right, min_key)
        return current

def _find_min_key(self, node):
        while node.left is not None:
            node = node.left
        return node.key

def inorder_traversal(self):
        self._inorder_recursive(self.root)

def _inorder_recursive(self, node):
        if node is not None:
            self._inorder_recursive(node.left)
            print(node.key, end=" ")
            self._inorder_recursive(node.right)

In this implementation, we have two classes: Node and BinarySearchTree. The Node class represents a single node in the binary search tree, storing a key (or value) and references to the left and right child nodes.
The BinarySearchTree class manages the binary search tree and provides various methods:

insert(key): Inserts a new node with the given key into the tree, maintaining the ordering property.
search(key): Searches for a node with the given key in the tree and returns it if found, or None otherwise.
delete(key): Deletes a node with the given key from the tree while preserving the ordering property.
inorder_traversal(): Performs an inorder traversal of the tree and prints the keys in ascending order.

Here's an example of using the binary search tree implementation:
bst = BinarySearchTree()
bst.insert(50)
bst.insert(30)
bst.insert(20)
bst.insert(40)
bst.insert(70)
bst.insert(60)
bst.insert(80)

bst.inorder_traversal()  # Output: 20 30 40 50 60 70 80

bst.delete(40)
bst.inorder_traversal()  # Output: 20 30 50 60 70 80

Binary search trees are commonly used for efficient searching, insertion, and deletion operations. They provide a way to organize and retrieve data in logarithmic time complexity on average, making them suitable for scenarios that require ordered data storage and retrieval.

What is a binary search tree in Python?

Similar Questions

What is a binary search tree in Python?

Jayant Kumar @jayantkumar314

Similar Questions