jsschools

Binary Search Tree (BST)

A binary tree where every node's left subtree contains only smaller values and its right subtree contains only larger values, enabling O(log n) average-case search.

Spec ↗

Syntax

class BST {
  #root = null;
  insert(val) { ... }
  search(val) { ... }
  delete(val) { ... }
}

Parameters

NameTypeRequiredDescription
compareFn function No Optional comparator (a, b) => number for custom ordering. Defaults to numeric/lexicographic natural ordering.

Returns

BST — A new Binary Search Tree instance.

Examples

class BSTNode {
  constructor(val) { this.val = val; this.left = null; this.right = null; }
}
class BST {
  #root = null;
  insert(val) {
    const node = new BSTNode(val);
    if (!this.#root) { this.#root = node; return; }
    let cur = this.#root;
    while (true) {
      if (val < cur.val) {
        if (!cur.left) { cur.left = node; return; }
        cur = cur.left;
      } else {
        if (!cur.right) { cur.right = node; return; }
        cur = cur.right;
      }
    }
  }
  search(val) {
    let cur = this.#root;
    while (cur) {
      if (val === cur.val) return true;
      cur = val < cur.val ? cur.left : cur.right;
    }
    return false;
  }
  inorder(node = this.#root, out = []) {
    if (node) { this.inorder(node.left, out); out.push(node.val); this.inorder(node.right, out); }
    return out;
  }
}
const bst = new BST();
[5, 3, 7, 1, 4, 6, 8].forEach(v => bst.insert(v));
console.log(bst.inorder());
console.log(bst.search(4), bst.search(9));
Output 
[ 1, 3, 4, 5, 6, 7, 8 ]
true false

// Kth smallest in a BST (in-order gives sorted order)
function kthSmallest(root, k) {
  let count = 0, result;
  function inorder(node) {
    if (!node || count >= k) return;
    inorder(node.left);
    if (++count === k) { result = node.val; return; }
    inorder(node.right);
  }
  inorder(root);
  return result;
}
Output 
(returns the kth smallest value from the BST)

Notes

| Operation | Best | Avg | Worst | Space | |----------|-------|--------|-------|-------| | Search | O(1) | O(log n)| O(n) | O(h) | | Insert | O(log n)| O(log n)| O(n)| O(h) | | Delete | O(log n)| O(log n)| O(n)| O(h) | h = height. An unbalanced BST degenerates to O(n) for sorted input. Use AVL or Red-Black trees for guaranteed O(log n). In-order traversal of a BST always yields sorted values — the key invariant.

See also