What does a binary search tree (BST) do?

AlgorithmsJunior~3 min read

Short answer

A binary search tree (BST) is a data structure where, for every node, all keys in the left subtree are less than the node's key, and all keys in the right subtree are greater. Thanks to this, a BST supports searching, inserting, and deleting elements in O(log n) on average, and an in-order traversal returns the elements in sorted order.

Detailed answer

What a BST is and why it is needed

A BST organizes a dynamic set of comparable keys so that search, insertion, and deletion can be performed quickly, and elements can be retrieved in sorted order without extra sorting. It is used to implement ordered sets and maps, range queries, nearest-value search, predecessor/successor lookups, and so on.

BST invariants

For every node: all keys in the left subtree are < the node's key, all keys in the right subtree are > the node's key.
The invariant is recursive: it holds for every node of the tree.
A duplicate-key policy is a design choice: forbid duplicates, keep a frequency counter, store a collection, or send equal keys to one side consistently (to the right, in the example).

Complexity of operations

Search/insert/delete: average O(log n), worst case O(n) on degeneration (if the tree becomes a "chain").
Traversal (in-order, pre-order, post-order): O(n).
Memory: O(n). The height h affects the operations: the smaller h is, the faster they are.
Balanced variants (AVL trees, red-black trees, and others) guarantee O(log n) in the worst case.

Main operations

Search: start at the root and go left or right depending on the comparison of the key with the current node's key, until you find it or hit an empty spot.
Insertion: look for the position the same way as in search, and insert the new node into the empty position found, preserving the invariant.
Deletion: three cases with respect to the node being deleted.

Leaf: simply remove it.
One child: pull the child up into the node's place.
Two children: replace the node's key (and value) with the key of its in-order successor (the minimum in the right subtree) and delete the successor from the right subtree.

Traversals: an in-order traversal returns a sorted sequence of keys.

Pre-order (root, left, right) - serializes the structure.
In-order (left, root, right) - sorted output.
Post-order (left, right, root) - deletion/deallocation.

Code example (JavaScript)

Duplicate-key policy: equal keys are sent to the right. You can pass your own comparison function.

class Node {
  constructor(key, value = null) {
    this.key = key;
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BST {
  constructor(compareFn) {
    this.root = null;
    this.compare = compareFn || ((a, b) => (a < b ? -1 : a > b ? 1 : 0));
  }

  contains(key) {
    let cur = this.root;
    while (cur) {
      const c = this.compare(key, cur.key);
      if (c === 0) return true;
      cur = c < 0 ? cur.left : cur.right;
    }
    return false;
  }

  search(key) {
    let cur = this.root;
    while (cur) {
      const c = this.compare(key, cur.key);
      if (c === 0) return cur.value ?? cur.key;
      cur = c < 0 ? cur.left : cur.right;
    }
    return undefined;
  }

  insert(key, value = null) {
    const node = new Node(key, value);
    if (!this.root) {
      this.root = node;
      return this;
    }
    let cur = this.root;
    while (true) {
      const c = this.compare(key, cur.key);
      if (c < 0) {
        if (!cur.left) { cur.left = node; break; }
        cur = cur.left;
      } else { // c >= 0 - duplicates are sent to the right
        if (!cur.right) { cur.right = node; break; }
        cur = cur.right;
      }
    }
    return this;
  }

  min(node = this.root) {
    if (!node) return undefined;
    while (node.left) node = node.left;
    return node.key;
  }

  max(node = this.root) {
    if (!node) return undefined;
    while (node.right) node = node.right;
    return node.key;
  }

  remove(key) {
    this.root = this.#removeNode(this.root, key);
    return this;
  }

  #removeNode(node, key) {
    if (!node) return null;
    const c = this.compare(key, node.key);
    if (c < 0) {
      node.left = this.#removeNode(node.left, key);
      return node;
    } else if (c > 0) {
      node.right = this.#removeNode(node.right, key);
      return node;
    } else {
      // Case 1: leaf
      if (!node.left && !node.right) return null;
      // Case 2: one child
      if (!node.left) return node.right;
      if (!node.right) return node.left;
      // Case 3: two children - take the successor (the minimum in the right subtree)
      let succ = node.right;
      while (succ.left) succ = succ.left;
      node.key = succ.key;
      node.value = succ.value;
      node.right = this.#removeNode(node.right, succ.key);
      return node;
    }
  }

  traverseInOrder(cb, node = this.root) {
    if (!node) return;
    this.traverseInOrder(cb, node.left);
    cb(node);
    this.traverseInOrder(cb, node.right);
  }

  traversePreOrder(cb, node = this.root) {
    if (!node) return;
    cb(node);
    this.traversePreOrder(cb, node.left);
    this.traversePreOrder(cb, node.right);
  }

  traversePostOrder(cb, node = this.root) {
    if (!node) return;
    this.traversePostOrder(cb, node.left);
    this.traversePostOrder(cb, node.right);
    cb(node);
  }

  height(node = this.root) {
    if (!node) return -1; // height of an empty tree
    return 1 + Math.max(this.height(node.left), this.height(node.right));
  }
}

Usage examples

const bst = new BST();
[8, 3, 10, 1, 6, 14, 4, 7, 13].forEach(k => bst.insert(k));

console.log('contains 7?', bst.contains(7)); // true
console.log('min/max:', bst.min(), bst.max()); // 1 14

const sorted = [];
bst.traverseInOrder(n => sorted.push(n.key));
console.log('sorted:', sorted.join(', ')); // 1, 3, 4, 6, 7, 8, 10, 13, 14

bst.remove(3);
const after = [];
bst.traverseInOrder(n => after.push(n.key));
console.log('after delete 3:', after.join(', '));

console.log('height:', bst.height());

// Range query [4, 10]
const range = [];
bst.traverseInOrder(n => {
  if (n.key >= 4 && n.key <= 10) range.push(n.key);
});
console.log('range [4..10]:', range.join(', '));

When a BST is a good choice

You need an ordered set with frequent insertions/deletions and fast lookups.
Range queries (all keys between L and R), predecessor/successor search.
You need to retrieve elements in sorted order "on the fly" (in-order traversal).

Pitfalls and tips

Worst-case degeneration: use random insertions, or use self-balancing trees for O(log n) guarantees.
Define and stick to a duplicate-key policy (forbid, count, or route right/left).
The comparison function must define a strict weak ordering (transitivity, irreflexivity) - otherwise the tree breaks.
Recursive implementations are simpler, but can hit the stack limit on very deep trees; use iterative versions if needed.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.