BST — Explained with Examples

A Binary Search Tree (BST) is a binary tree where each node’s left subtree contains smaller values and the right subtree larger values.

BST maintains the property: for any node, all values in its left subtree are less than the node’s value, and all values in its right subtree are greater. This property enables O(log n) average-case search, insertion, and deletion when the tree is balanced. Inorder traversal of a BST yields sorted order. Without balancing (e.g., inserting sorted data), a BST can degenerate into a linked list with O(n) operations.

Think of a BST like a well-organized filing cabinet. You open the top drawer (root). If the file you want comes before ‘M’, you look left; if after, you look right. Each drawer you open eliminates half the remaining files — you find what you need in seconds instead of searching every file.

Self-balancing BST variants like AVL trees and red-black trees maintain O(log n) height guarantees through rotation operations after insertions and deletions.

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

    def __init__(self):
        self.root = None

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

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

bst = BST()
for v in [5, 3, 7, 1, 4]:
    bst.insert(v)
print(bst.search(4))  # True
print(bst.search(6))  # False

BSTs are used in database indexes, in-memory sorted collections, and symbol tables. The ordered structure enables range queries and nearest-neighbor search.

Binary Tree, Hash Table, Heap, Sorting Algorithms

Binary Tree Overview