Binary search tree

O(log n) avg

A binary tree kept ordered so that every node's left subtree is smaller and its right subtree is larger, letting search, insert, and delete each discard half the remaining nodes.

Signals

binary search tree: left < node < right at every nodeinsert/delete/search while keeping the data orderedvalidate BST / kth smallest / inorder traversal gives sorted orderclosest value or range query on a set that changes over timeno array given up front, values arrive one at a time

Template

function insert(node, val) {
    if (!node) return { val, left: null, right: null };
    if (val < node.val) node.left = insert(node.left, val);
    else if (val > node.val) node.right = insert(node.right, val);
    return node;
}

Looks similar, isn't

Binary search on a sorted array: A BST is a dynamic sorted set: it supports insert and delete while keeping order, and inorder traversal always yields the current sorted sequence. Plain binary search assumes a static sorted array that is not being mutated while you search it.

n nodes, roughly balanced -> O(log n) average per search/insert/delete because each comparison discards one whole subtree. Degenerates to O(n) worst case if the tree becomes a chain (e.g. sorted input inserted in order).

Learn this pattern