Learn how the BST ordering property enables fast search, insert, and delete in O(log n).

Binary Search Tree

A binary search tree (BST) is a binary tree with one extra rule: for every node, all values in its left subtree are smaller, and all values in its right subtree are larger. This single rule is what makes search, insert, and delete all run in O(log n) on a balanced tree — the same speedup binary search gives over linear search.

              50
            /    \
          30      70
         /  \    /  \
       20   40  60   80

Every left value < parent. Every right value > parent. Always.

Binary Search Treeleft < parent < right

Search or insert a value to see the BST property in action

Search — O(log n)

At each node, compare the target with the current value. Go left if smaller, right if larger. Each comparison eliminates an entire subtree — exactly like binary search on a sorted array.

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


def search(node, target):
    if node is None:
        return False   # not found

    if target == node.value:
        return True    # found

    if target < node.value:
        return search(node.left, target)
    else:
        return search(node.right, target)

Insert — O(log n)

Walk down the tree following the same left/right rule used in search. Insert the new node at the first empty spot found.

def insert(node, value):
    if node is None:
        return TreeNode(value)   # found the spot — create the node

    if value < node.value:
        node.left = insert(node.left, value)
    elif value > node.value:
        node.right = insert(node.right, value)
    # if value == node.value, typically ignore duplicates

    return node


root = None
for val in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, val)

Delete — O(log n), three cases

Deletion is the trickiest BST operation because removing a node must preserve the ordering property for everything left behind.

Case 1 — node is a leaf: Just remove it.

Case 2 — node has one child: Replace the node with its child.

Case 3 — node has two children: Replace the node's value with its in-order successor (the smallest value in the right subtree), then delete that successor from the right subtree.

def delete(node, value):
    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:
        # found the node to delete

        # case 1 — no children, or case 2 — one child
        if node.left is None:
            return node.right
        if node.right is None:
            return node.left

        # case 3 — two children
        # find the smallest value in the right subtree
        successor = node.right
        while successor.left:
            successor = successor.left

        node.value = successor.value
        node.right = delete(node.right, successor.value)

    return node

Why the in-order successor works

The in-order successor is the smallest value greater than the deleted node. It is guaranteed to have at most one child (no left child, since it is the leftmost node of the subtree) — so replacing the deleted node's value with it, then removing the successor from its original spot, is always a simple case 1 or case 2 deletion.

Delete 30 (has two children, 20 and 40):

       50                    50
      /  \                  /  \
    30    70    →         40    70
   /  \                  /
  20   40               20

30 replaced by 40 (smallest in right subtree),
then 40 removed from its original position.

Min and max

def find_min(node):
    """Leftmost node — smallest value."""
    while node.left:
        node = node.left
    return node.value


def find_max(node):
    """Rightmost node — largest value."""
    while node.right:
        node = node.right
    return node.value

The catch — balance matters

Search, insert, and delete are all O(log n) only if the tree is balanced. If values are inserted in sorted order, the BST degenerates into a straight line — a linked list — and every operation becomes O(n).

# inserting already-sorted values creates a degenerate tree
root = None
for val in [10, 20, 30, 40, 50]:
    root = insert(root, val)

#  10
#    \
#     20
#       \
#        30
#          \
#           40
#             \
#              50

A plain BST does not guarantee balance. Self-balancing trees like AVL trees and Red-Black trees automatically rebalance after every insert and delete, guaranteeing O(log n) in the worst case. Python's standard library does not include one built-in, but sortedcontainers.SortedList is a popular alternative that achieves similar guarantees.

Complexity

Operation	Average (balanced)	Worst case (degenerate)
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)
Find min/max	O(log n)	O(n)

Binary Search Tree

On this page