Binary Search Trees — O(log n) Search

Build the mental model

A binary search tree (BST) adds one invariant on top of a plain binary tree: for every node, all values in its left subtree are smaller and all values in its right subtree are larger. That invariant turns search into binary search performed on a tree shape — compare the target against the current node, then descend only into the left or right subtree depending on the comparison, eliminating half the remaining candidates at every step. For a balanced tree this makes the height O(log n), so both search and insert are O(log n). But that guarantee depends entirely on the tree's shape: inserting already-sorted data (1, 2, 3, 4, 5, in order) produces a tree where every node has only a right child — a chain of height n, which is a linked list in disguise, and search degrades to O(n) with no balance guarantee left. Self-balancing BST variants like AVL trees and Red-Black trees exist to fix exactly this, using rotations on every insert/delete to keep height at O(log n) regardless of insertion order — this lesson won't implement one, but it's worth knowing why they exist.

Connect it to a real scenario

If the Tutorial Platform keeps its lesson slugs in a sorted BST, it can search in O(log n) — slower than a dict hash lookup, but a BST can answer range queries ("all slugs between 'a' and 'm'") that a hash-based dict simply can't. The catch to watch for: bulk-importing a course's lessons in alphabetical order would produce a skewed tree and degrade search back to O(n).

• BST invariant: for every node, left subtree < node < right subtree
• In a balanced BST, search/insert are O(log n) since each step eliminates half the remaining candidates
• Inserting already-sorted data turns a BST into a chain, degrading to O(n) — AVL/Red-Black trees exist to fix this

Try the working example

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

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

def search(node, value):
    if node is None:
        return False
    if value == node.value:
        return True
    if value < node.value:
        return search(node.left, value)
    return search(node.right, value)

root = None
for slug in ["queues", "hash-tables", "stacks", "binary-trees", "linked-lists"]:
    root = insert(root, slug)

print(search(root, "stacks"))
print(search(root, "recursion"))

Prints True ("stacks" exists in the tree) followed by False ("recursion" was never inserted).

Wikipedia — Binary search tree — Data Structures & Algorithms