Binary Search Tree (BST)

Prev Next

A Binary Search Tree is a regular binary tree with exactly one extra rule applied at every single node, and that one rule is what turns "a tree" into "a structure you can search in O(log n)." This lesson codes insert, search, and delete against that rule, then shows exactly why the O(log n) claim is an average-case claim, not a guarantee.

The BST Invariant

For every node in the tree:

Every value in its left subtree is less than the node's value.
Every value in its right subtree is greater than the node's value.

This holds recursively at every node, not just the root. The left child of the root must itself have a smaller left subtree and a larger (but still smaller than the root) right subtree, and so on all the way down. This is exactly why inorder traversal of a BST visits nodes in sorted order — it's the direct consequence of this invariant.

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

Insert

To insert a value, walk from the root: go left if the new value is smaller, right if it's larger, and when you fall off the tree (hit None), that's where the new node goes.

def insert(root, value):
    if root is None:
        return TreeNode(value)          # base case: found the empty spot
    if value < root.val:
        root.left = insert(root.left, value)
    elif value > root.val:
        root.right = insert(root.right, value)
    # value == root.val: duplicate, no-op (BSTs commonly disallow duplicates)
    return root

Time complexity: O(h) — one comparison per level, where h is the tree's height (O(log n) average, O(n) worst case — see below). Space complexity: O(h) — recursion stack depth equals the path walked.

Search

def search(root, target):
    if root is None:
        return False                    # fell off the tree without finding it
    if target == root.val:
        return True
    if target < root.val:
        return search(root.left, target)
    return search(root.right, target)

Time complexity: O(h) — at each step exactly one comparison eliminates the entire opposite subtree from consideration, same height bound as insert. Space complexity: O(h) — recursion stack.

Why this beats a plain sorted list for insertion: binary search on a sorted list finds a value in O(log n) too, but inserting into a sorted list is O(n) because Python has to shift every element after the insertion point (the same cost as Python's own list.insert() in the middle of a list). A BST gets O(log n) search-like behavior for insert too, because there's no shifting — you just attach a new node.

Delete

Delete is the trickiest of the three because removing a node with two children would leave a gap — you can't just discard it. The standard approach: find the node's inorder successor (the smallest value in its right subtree — walk left-child pointers as far as possible from root.right), copy that value up into the node being "deleted," and then delete the successor from the right subtree instead (which is guaranteed to be the easy case, since the successor has no left child by definition).

def delete(root, value):
    if root is None:
        return None                     # value not found, nothing to do

    if value < root.val:
        root.left = delete(root.left, value)
    elif value > root.val:
        root.right = delete(root.right, value)
    else:
        # found the node to delete
        if root.left is None:
            return root.right             # 0 or 1 child (right): promote right child
        if root.right is None:
            return root.left              # 1 child (left): promote left child

        # 2 children: find inorder successor = leftmost node of right subtree
        successor = root.right
        while successor.left is not None:
            successor = successor.left
        root.val = successor.val                       # copy successor's value up
        root.right = delete(root.right, successor.val)  # remove the successor's original node
    return root

Time complexity: O(h) — locating the node is O(h), and locating the successor is bounded by another O(h) walk down the right subtree, so total is still O(h). Space complexity: O(h) — recursion stack.

Average Case O(log n) vs Worst Case O(n)

Every operation above costs O(h), where h is the tree's height. The O(log n) claim you hear about BSTs is really a claim about h — and h is only O(log n) when the tree is reasonably balanced (roughly the same number of nodes on the left and right of every subtree). Nothing in the insert code above enforces that. Insert data in a bad order, and the tree degenerates.

# Inserting already-sorted data, in order, into an empty BST:
root = None
for value in [1, 2, 3, 4, 5, 6]:
    root = insert(root, value)

Every new value is larger than everything already in the tree, so every
insert goes right, and only right. The "tree" becomes a straight line:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

This is a "degenerate" or "skewed" tree -- height h = n = 6, not log2(6) ~ 2.6.
Searching for 6 now means walking through 1, 2, 3, 4, 5 first: a linked list
wearing a TreeNode costume.
          

Search, insert, and delete on this degenerate tree all cost O(n) — you've lost every advantage a BST was supposed to give you over a plain list, while paying extra memory for left/right references you never use.

Operation	Average case (balanced-ish tree)	Worst case (skewed tree)
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)

The takeaway an interviewer wants to hear: "BST operations are O(log n) on average, but O(n) worst case if the tree becomes skewed — for example by inserting sorted or near-sorted data." Saying "BSTs are O(log n)" with no caveat is the kind of gloss that gets follow-up questions.

Up next: Balanced Trees (Intro) exists to solve exactly this problem — structures like AVL trees and Red-Black trees automatically re-balance after every insert/delete so height stays O(log n) no matter what order the data arrives in. First, though, Heaps & Priority Queue covers a different tree-shaped structure built for a different job: always knowing the smallest (or largest) element instantly.

Prev Next