Binary Search Trees

A binary search tree (BST) is a binary tree that keeps its values in sorted order by enforcing one rule at every node: everything in the left subtree is smaller than the node, and everything in the right subtree is larger. That single ordering rule is what makes BSTs powerful — it lets you search, insert, and delete in roughly logarithmic time without ever fully scanning the data, and it lets you read the values back out in sorted order for free. BSTs are also the foundation for the self-balancing structures (AVL trees, red-black trees) used inside many real database indexes.

Overview / How it Works

Picture inserting the numbers 50, 30, 70, 20, 40, 60, and 80, one at a time, into an empty tree. The first value, 50, becomes the root. Every value after that walks down from the root: at each node, compare the new value to that node’s value — go left if it’s smaller, go right if it’s larger — until you fall off the tree (reach None), which is exactly where the new node gets attached. Following that process: 30 is smaller than 50, so it attaches as 50’s left child. 70 is larger than 50, so it attaches as 50’s right child. 20 is smaller than 50 and smaller than 30, so it attaches as 30’s left child. 40 is smaller than 50 but larger than 30, so it attaches as 30’s right child. The same logic places 60 as 70’s left child and 80 as 70’s right child.

Notice what this guarantees: for any node, every value in its left subtree is smaller and every value in its right subtree is larger, not just its immediate children — the property holds recursively all the way down. That’s what lets an in-order traversal (left subtree, then node, then right subtree) print every value in ascending order, and it’s what lets search skip half the remaining tree at every step, the same divide-and-conquer idea as binary search on a sorted array.

Time and Space Complexity

A BST’s performance depends entirely on its height h — the number of edges on the longest root-to-leaf path — because search, insert, and delete all walk a single such path. If the tree is roughly balanced, h is about log2(n) for n nodes, since each comparison discards roughly half of the remaining nodes. But nothing in a plain BST forces it to stay balanced: insert already-sorted data and every new node only ever gets one child, so the tree degenerates into a linked list with height n. Example 3 below demonstrates exactly this gap between a balanced and a skewed tree built from the same seven values.

Operation	Average case	Worst case	Why
Search	O(log n)	O(n)	Walks one root-to-leaf path of length h; h is log n when balanced, n when skewed.
Insert	O(log n)	O(n)	Same root-to-leaf walk, stopping at the first empty spot.
Delete	O(log n)	O(n)	Same walk to find the node, plus a bounded walk to find an in-order successor when deleting a node with two children.
In-order traversal	O(n)	O(n)	Every node is visited exactly once, regardless of shape.

Space complexity for the tree itself is O(n) — one node object per value. The recursive implementations in this lesson also use O(h) additional space on the call stack (O(log n) balanced, O(n) skewed); an iterative version using an explicit loop instead of recursion would use O(1) extra space for search and insert, trading code clarity for that saving. Because Python’s default recursion limit is roughly 1000, a deeply skewed tree built from a very large sorted input could raise a RecursionError in a recursive implementation — one reason self-balancing variants exist for large, unpredictable datasets.

Examples

The three examples below build a BST, search and delete from it, and compare a balanced shape against a worst-case skewed one. Each is a complete script — paste it in and run it to see the exact output described.

Example 1: Building a BST, Searching It, and Reading It Back Sorted

class Node:
    def __init__(self, value: int) -> None:
        self.value = value
        self.left: "Node | None" = None
        self.right: "Node | None" = None


class BST:
    def __init__(self) -> None:
        self.root: "Node | None" = None

    def insert(self, value: int) -> None:
        self.root = self._insert(self.root, value)

    def _insert(self, node: "Node | None", value: int) -> Node:
        if node is None:
            return Node(value)
        if value < node.value:
            node.left = self._insert(node.left, value)
        elif value > node.value:
            node.right = self._insert(node.right, value)
        return node

    def search(self, value: int) -> bool:
        return self._search(self.root, value)

    def _search(self, node: "Node | None", value: int) -> bool:
        if node is None:
            return False
        if value == node.value:
            return True
        if value < node.value:
            return self._search(node.left, value)
        return self._search(node.right, value)

    def inorder(self) -> list[int]:
        result: list[int] = []
        self._inorder(self.root, result)
        return result

    def _inorder(self, node: "Node | None", result: list[int]) -> None:
        if node is None:
            return
        self._inorder(node.left, result)
        result.append(node.value)
        self._inorder(node.right, result)


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

print("In-order (sorted) traversal:", tree.inorder())
print("Search 40:", tree.search(40))
print("Search 90:", tree.search(90))

Output:

In-order (sorted) traversal: [20, 30, 40, 50, 60, 70, 80]
Search 40: True
Search 90: False

Inserting 50, 30, 70, 20, 40, 60, and 80 in that order produces the tree described in the Overview section. Calling inorder() walks the left subtree, then the node itself, then the right subtree, recursively — the result is every value printed in ascending order regardless of insertion order: [20, 30, 40, 50, 60, 70, 80]. search(40) starts at the root (50), goes left because 40 < 50, arrives at 30, goes right because 40 > 30, and finds 40 — three comparisons, True. search(90) goes right at every node (50 → 70 → 80) and then falls off the tree past 80, returning False.

Example 2: Deleting a Node with Two Children

class Node:
    def __init__(self, value: int) -> None:
        self.value = value
        self.left: "Node | None" = None
        self.right: "Node | None" = None


def insert(node: "Node | None", value: int) -> Node:
    if node is None:
        return Node(value)
    if value < node.value:
        node.left = insert(node.left, value)
    elif value > node.value:
        node.right = insert(node.right, value)
    return node


def find_min(node: Node) -> Node:
    current = node
    while current.left is not None:
        current = current.left
    return current


def delete(node: "Node | None", value: int) -> "Node | None":
    if node is None:
        return None
    if value < node.value:
        node.left = delete(node.left, value)
    elif value > node.value:
        node.right = delete(node.right, value)
    else:
        if node.left is None:
            return node.right
        if node.right is None:
            return node.left
        successor = find_min(node.right)
        node.value = successor.value
        node.right = delete(node.right, successor.value)
    return node


def inorder(node: "Node | None", result: list[int]) -> None:
    if node is None:
        return
    inorder(node.left, result)
    result.append(node.value)
    inorder(node.right, result)


root: "Node | None" = None
for value in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, value)

result: list[int] = []
inorder(root, result)
print("Before deletion:", result)

root = delete(root, 30)

result = []
inorder(root, result)
print("After deleting 30:", result)

Output:

Before deletion: [20, 30, 40, 50, 60, 70, 80]
After deleting 30: [20, 40, 50, 60, 70, 80]

The script builds the same seven-node tree, prints its sorted contents, then deletes 30 — a node with two children (20 and 40). The delete function replaces 30’s value with its in-order successor: the smallest value in its right subtree. find_min walks left from the subtree rooted at 40 and immediately returns 40 itself, since 40 has no left child. The node that used to hold 30 now holds the value 40, and the recursive call then deletes the original leaf node 40 from the right subtree, leaving that link empty. The result, [20, 40, 50, 60, 70, 80], is still six values in strict sorted order with no gaps or duplicates — exactly what deleting one value from a seven-value BST should produce.

Example 3: Balanced vs. Skewed — Why Insertion Order Matters

class Node:
    def __init__(self, value: int) -> None:
        self.value = value
        self.left: "Node | None" = None
        self.right: "Node | None" = None


def insert(node: "Node | None", value: int) -> Node:
    if node is None:
        return Node(value)
    if value < node.value:
        node.left = insert(node.left, value)
    elif value > node.value:
        node.right = insert(node.right, value)
    return node


def height(node: "Node | None") -> int:
    if node is None:
        return -1
    return 1 + max(height(node.left), height(node.right))


balanced_root: "Node | None" = None
for value in [50, 30, 70, 20, 40, 60, 80]:
    balanced_root = insert(balanced_root, value)

skewed_root: "Node | None" = None
for value in [10, 20, 30, 40, 50, 60, 70]:
    skewed_root = insert(skewed_root, value)

print("Balanced tree height:", height(balanced_root))
print("Skewed tree height:", height(skewed_root))

Output:

Balanced tree height: 2
Skewed tree height: 6

Inserting [50, 30, 70, 20, 40, 60, 80] produces the same bushy tree as before — root, two children, four grandchildren — so its height (edges from root to the deepest leaf) is 2. Inserting [10, 20, 30, 40, 50, 60, 70], which is already sorted, means every new value is larger than everything inserted so far, so each one becomes the right child of the previous node, producing a straight seven-node chain with six edges from root to the final leaf, so its height is 6. Both trees hold the same seven values, but the skewed tree is three times taller, which means searches on it can take up to three times as many comparisons — this is exactly why insertion order matters for a plain BST.

How it Works Step by Step

Take the tree from Example 1 and insert one more value, 65, to see exactly how the comparisons unfold:

1. Start at the root, 50. Since 65 is greater than 50, move right.
2. Now at 70. Since 65 is less than 70, move left.
3. Now at 60. Since 65 is greater than 60, move right.
4. 60’s right child is empty (None), so 65 is attached there as a new leaf.

Three comparisons placed the value correctly — that’s O(h) work, not O(n), because each comparison eliminates an entire subtree from consideration instead of checking every node individually. Searching for a value follows the identical path-following logic; the only difference is that search stops and returns True the moment it finds an equal value, or False if it falls off the tree without finding one.

Common Mistakes

Mistake 1: Discarding the Recursive Return Value

A very common bug is calling a recursive insert helper but throwing away what it returns:

def insert_wrong(node, value):
    if node is None:
        node = Node(value)
    elif value < node.value:
        insert_wrong(node.left, value)
    elif value > node.value:
        insert_wrong(node.right, value)
    return node

When node is None, reassigning the local variable node inside the function does nothing to the caller’s node.left or node.right attribute — Python passes object references by value, so rebinding a local name never changes what the parent’s pointer points to. The new node gets created and then silently lost; insert_wrong raises no error, but the value never actually attaches to the tree. The fix is to always reassign the child link with the recursive call’s return value:

def insert_correct(node, value):
    if node is None:
        return Node(value)
    if value < node.value:
        node.left = insert_correct(node.left, value)
    elif value > node.value:
        node.right = insert_correct(node.right, value)
    return node

Each recursive call returns the (possibly newly created) subtree root, and the caller explicitly wires it back into node.left or node.right. This is the same pattern the working insert and delete functions in the examples above rely on, and it’s worth internalizing since it shows up constantly in recursive tree code.

Mistake 2: A Mutable Default Argument in a Collector Helper

It’s tempting to give a recursive "collect values into a list" helper a default empty list so callers don’t have to pass one in:

def collect_values_wrong(node, result=[]):
    if node is None:
        return result
    collect_values_wrong(node.left, result)
    result.append(node.value)
    collect_values_wrong(node.right, result)
    return result

Default argument values in Python are evaluated once, when the function is defined, not once per call. That single list object is reused across every call that doesn’t explicitly pass its own result, so values from one call silently accumulate into the next: call collect_values_wrong(tree_a) and then collect_values_wrong(tree_b), and the second result still contains tree_a‘s values mixed in. The fix is to default to None and create a fresh list inside the function body:

def collect_values_correct(node, result=None):
    if result is None:
        result = []
    if node is None:
        return result
    collect_values_correct(node.left, result)
    result.append(node.value)
    collect_values_correct(node.right, result)
    return result

This "default to None, initialize inside" pattern applies to any recursive or backtracking function that accumulates results into a list, set, or dict argument — not just tree traversals.

Best Practices

• Use a plain BST when insertions arrive in a roughly random order — in that scenario it behaves close to its O(log n) average case with far less code than a self-balancing tree.
• If insertions can arrive already sorted, or in an adversarial order, reach for a self-balancing structure (AVL tree, red-black tree) or Python’s bisect module on a sorted list instead — a plain BST offers no protection against degenerating into a linked list.
• An in-order traversal of a BST always yields values in ascending sorted order — use this property instead of sorting separately when the data is already in a BST.
• When validating whether a tree is a valid BST, compare each node against a running lower/upper bound inherited from its ancestors, not just against its immediate children — checking only immediate children misses violations further down the tree.
• Prefer iterative implementations with an explicit while loop for search and insert on very large or potentially skewed trees, to avoid RecursionError from Python’s recursion limit.
• Don’t reach for a BST just to check membership if you don’t need sorted order or range queries — a set or dict gives O(1) average lookup, which beats a BST’s O(log n) average case.

Practice Exercises

1. Write a function kth_smallest(root, k) that returns the k-th smallest value in a BST using an in-order traversal. For the tree built from [50, 30, 70, 20, 40, 60, 80], kth_smallest(root, 3) should return 40.
2. Write find_min(root) and find_max(root) functions that return the minimum and maximum values in a BST without visiting every node. Hint: the minimum is always the leftmost node, the maximum always the rightmost.
3. Write is_valid_bst(root) that returns True or False for whether a binary tree satisfies the BST property, using the lower/upper bound technique from the Best Practices section. Test it on a tree that looks valid from any single node’s immediate children but violates the property two levels down, to confirm your solution catches it where a same-immediate-children check would not.

Summary

• A binary search tree keeps every left subtree smaller and every right subtree larger than its parent, which enables O(log n) average search, insert, and delete by discarding roughly half the remaining nodes at each step.
• Worst-case performance degrades to O(n) when the tree becomes skewed (for example, inserting already-sorted data), because height h can grow to n instead of staying near log n.
• Deleting a node with two children works by replacing its value with its in-order successor (the minimum of its right subtree) and then deleting that successor instead.
• In-order traversal of a BST always produces values in ascending sorted order — an O(n) operation that visits every node exactly once.
• Always reassign the return value of a recursive insert or delete call back into node.left/node.right; never use a mutable object as a default argument.
• Self-balancing trees (AVL, red-black) exist specifically to guarantee O(log n) height regardless of insertion order — reach for one, or a set/dict, when a plain BST’s worst case is a real risk.