Binary Search Tree: Definition, Example, and Uses

A binary search tree (BST) is a special type of tree data structure where each node has at most two children, called left and right. The left child's value is always less than its parent node's value, and the right child's value is always greater, which allows fast searching, insertion, and deletion.

How It Works

A binary search tree organizes data in a way that makes searching very efficient. Imagine a family tree where each person has up to two children. In a BST, the left child always holds a smaller number than the parent, and the right child holds a larger number. This rule applies to every node in the tree.

When you want to find a number, you start at the top (called the root). If the number you want is smaller than the root, you go left; if it's bigger, you go right. You keep doing this until you find the number or reach a point where it doesn't exist. This method is like looking for a word in a dictionary by opening to the middle and deciding which half to search next.

Example

This example shows how to create a simple binary search tree, insert values, and search for a value.

python

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

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

    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
            return
        current = self.root
        while True:
            if value < current.value:
                if current.left is None:
                    current.left = Node(value)
                    return
                current = current.left
            else:
                if current.right is None:
                    current.right = Node(value)
                    return
                current = current.right

    def search(self, value):
        current = self.root
        while current:
            if value == current.value:
                return True
            elif value < current.value:
                current = current.left
            else:
                current = current.right
        return False

# Example usage
bst = BinarySearchTree()
bst.insert(10)
bst.insert(5)
bst.insert(15)
bst.insert(7)
print(bst.search(7))
print(bst.search(3))

Output

True
False

When to Use

Binary search trees are useful when you need to store data that you want to search, add, or remove quickly. They work well when the data is mostly sorted or when you want to keep it sorted as you add new items.

Common real-world uses include managing sorted lists, database indexing, and implementing priority queues. For example, a phone book app might use a BST to quickly find a contact by name.

Key Points

• A BST keeps data in a sorted order for fast searching.
• Each node has up to two children: left (smaller) and right (larger).
• Searching, inserting, and deleting can be done efficiently if the tree is balanced.
• Performance can degrade if the tree becomes unbalanced, turning into a list.

Key Takeaways

A binary search tree stores data so that left children are smaller and right children are larger than their parent nodes.

It allows fast searching by deciding to go left or right at each step, like looking up words in a dictionary.

BSTs are useful for sorted data storage and quick insertions, deletions, and lookups.

Keeping the tree balanced is important to maintain efficient operations.

BSTs are widely used in databases, search algorithms, and real-time data management.