A Binary Search Tree (BST) is a binary tree with one extra rule layered on top: for every node, everything in its left subtree is smaller, and everything in its right subtree is larger. That single ordering invariant is what turns a plain tree into a structure that can search, insert, and delete in O(log n) time on average — without the fixed capacity problems of a sorted array.

This makes BSTs a natural middle ground between a sorted array (fast search, but O(n) insertion since you have to shift elements) and a linked list (fast insertion, but O(n) search).

Inserting and Searching

Both operations follow the same logic: start at the root, and at each node, go left if your target is smaller or right if it's larger, repeating until you either find the value or run out of tree.

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

class BST:
    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
            current = current.left if value < current.value else current.right
        return False

tree = BST()
for n in [50, 30, 70, 20, 40, 60, 80]:
    tree.insert(n)

print(tree.search(40))
print(tree.search(99))

Output:

True
False

Each comparison eliminates roughly half the remaining tree — the same logic behind binary search on a sorted array, except the BST's shape makes insertion cheap too. You can see a full working implementation, including delete and traversal, in the Python BST program.

Why Search Is O(log n) — Usually

Every comparison moves you one level deeper and discards an entire subtree you now know doesn't contain the value. For a tree with n nodes arranged in a roughly balanced shape, the height is about log₂(n), so search, insert, and delete all cost O(log n).

The Degenerate Tree Problem

That O(log n) guarantee depends entirely on the tree staying balanced. If you insert already-sorted data — 10, 20, 30, 40, 50 — every new node becomes the right child of the previous one, and the "tree" collapses into a straight line. At that point you've accidentally built a linked list, and search degrades to O(n).

degenerate = BST()
for n in [10, 20, 30, 40, 50]:   # already sorted — worst case input
    degenerate.insert(n)
# This tree has height 5, not log2(5) ~ 2.3 — every node has only a right child

This is exactly the problem self-balancing trees like AVL trees solve — they automatically restructure themselves after insertions to keep the height close to log(n), no matter what order the data arrives in. For most everyday use, a plain BST is simple and fast enough; reach for a self-balancing variant when your input order can't be trusted.