search

How to implement a binary search tree in Python?

To implement a binary search tree (BST) in Python, you can define two classes: Node and BinarySearchTree. The Node class represents an individual node in the binary search tree, while the BinarySearchTree class manages the tree and provides methods for insertion, search, deletion, and traversal. Here's an example implementation:

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 < 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 < 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 < 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, the Node class represents a single node in the binary search tree. It has an attribute key to store the value of the node, and left and right attributes to hold references to the left and right child nodes, respectively.

The BinarySearchTree class manages the binary search tree and provides several methods:

  • insert(key): Inserts a new node with the given key into the tree, maintaining the binary search tree 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 binary search tree 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

This implementation demonstrates the basic operations of a binary search tree, including insertion, deletion, and traversal. You can further extend it by adding other functionalities like preorder and postorder traversals, finding the minimum or maximum key, or balancing the tree.

Related Questions You Might Be Interested