bstrees

Sorted sets backed by binary search trees: a self-balancing AVLTree and a plain BSTree. Values are kept in order by a comparator, so besides lookups you get ordered iteration, range queries and nearest-value searches.

• Set-like API: insert, has, get, getOrInsert, delete, clear
• Ordered queries: min, max, popMin, popMax, floor, ceil, lower, higher, range, reverse iteration
• Iterators that support iterator helpers and tolerate modifications
• No dependencies, no recursion, fully typed

Installation

npm install bstrees
Copy

Requires Node.js 24 or newer. The package is an ES module; require("bstrees") works too through Node.js require(esm).

TypeScript users need TypeScript 5.6 or newer. Two compiler options matter:

• the iterator helpers (tree.values().filter(...)) are typed only with the esnext library (or es2025 on TypeScript 6), for example "lib": ["esnext"];
• a CommonJS project that requires the package needs "module": "nodenext" and TypeScript 5.8 or newer.

In generic code over primitive types (T extends number), TypeScript cannot tell that the default comparator applies, so new AVLTree<T>() needs a comparator. Use AVLTree.from<T>(values) or AVLTree.from<T>([]) instead.

Quick start

import { AVLTree } from "bstrees";

const tree = AVLTree.from([5, 1, 4, 2, 3]);

tree.insert(6); // true
tree.insert(6); // false: the value is already stored
tree.has(4); // true
tree.delete(1); // true
tree.toArray(); // [2, 3, 4, 5, 6]
tree.floor(4.5); // 4
tree.ceil(4.5); // 5
[...tree.range({ gte: 3, lt: 5 })]; // [3, 4]
tree.popMax(); // 6
Copy

Choosing a tree

Tree	Lookup, insert, delete	Notes
AVLTree	O(log n)	Self-balancing. Use it by default.
BSTree	O(log n) average, O(n) worst	No rebalancing. Inserting values in sorted order degrades it into a list.

BSTree is only O(log n) on average for values inserted in random order. Removing a node with two children always moves its successor up, so a long-lived tree with many random removals and insertions gets deeper over time (towards √n). Use AVLTree for such workloads.

Both trees share the SortedTree<T> type. Use it to accept either of them.

Comparators

A tree orders its values with a comparator (a, b) => number. It returns:

• a negative number when a sorts before b;
• a positive number when a sorts after b;
• zero when they are equal.

Values are unique with respect to the comparator. Inserting a value equal to a stored one keeps the stored one.

The comparator must define a consistent total order:

• it returns 0 for equal arguments and never returns NaN;
• compare(a, b) and compare(b, a) have opposite signs;
• it is transitive;
• it gives the same result for the same stored values for as long as they are in the tree. Do not mutate the fields it reads.

The tree may call it with its arguments in either order, and calls it without a receiver: a strict-mode function gets this === undefined, a bound function keeps its bound this. If the comparator throws, the error propagates and the tree is left unchanged. A result that is not a number, or is NaN, throws a TypeError.

The comparator must not modify the tree it orders. The mutating methods (insert, getOrInsert, delete, clear, popMin, popMax) throw a TypeError when called from the comparator, before they change anything. Reading the tree or modifying other trees from the comparator is allowed, but some reads call the comparator again:

• size, height, min(), max() and a new iteration over all values (values(), valuesReversed(), forEach(), toArray()) of a tree that does not change meanwhile never call it;
• searches (has, get, floor, ceil, lower, higher), range and an iterator that resumes after the tree changed call it, so a comparator that uses them on its own tree must guard against infinite recursion.

Default comparator. It is used when no comparator is passed and handles numbers, strings and bigints:

• -0 equals 0;
• strings are compared by UTF-16 code units;
• NaN, values of different types and anything else (objects, dates, undefined, ...) throw a TypeError.

Every method that takes a value, including the bounds of range, passes it to the comparator even when the tree is empty, so has(NaN) throws whether the tree is empty or not. A value of another type, such as "1" in a tree of numbers, can only be detected once the tree holds a value to compare it with.

TypeScript requires a comparator for any other value type:

import { AVLTree, BSTree } from "bstrees";

// Descending numbers
const descending = new AVLTree<number>((a, b) => b - a);

// Locale-aware strings
const { compare } = new Intl.Collator("de");
const words = new AVLTree<string>(compare);

// Dates
const dates = new AVLTree<Date>((a, b) => a.getTime() - b.getTime());

// Records ordered by a key, with a tie-breaker
interface IUser {
  name: string;
  id: number;
}
const users = new BSTree<IUser>(
  (a, b) => a.name.localeCompare(b.name) || a.id - b.id,
);
Copy

Because only the comparator decides equality, get and getOrInsert can look up a stored record by a probe that only carries the key:

import { AVLTree } from "bstrees";

interface ILevel {
  price: number;
  orders: number[];
}

const book = new AVLTree<ILevel>((a, b) => a.price - b.price);

book.getOrInsert({ price: 10, orders: [] }).orders.push(1);
book.getOrInsert({ price: 10, orders: [] }).orders.push(2);
book.getOrInsert({ price: 12, orders: [] }).orders.push(3);

book.get({ price: 10, orders: [] })?.orders; // [1, 2]
book.min()?.price; // 10 (the lowest price)
Copy

API

Member	Description	AVLTree	BSTree
new AVLTree<T>(compare?)	Creates an empty tree (the comparator is optional for numbers, strings, bigints)	O(1)	O(1)
AVLTree.from(values, compare?)	Creates a tree from an iterable	O(n log n)	O(n·h)
size	Number of values	O(1)	O(1)
height	Edges on the longest root-to-leaf path (-1 when empty)	O(1)	O(1)
has(value)	Whether an equal value is stored	O(log n)	O(h)
get(value)	The stored value equal to value, or undefined	O(log n)	O(h)
insert(value)	Inserts unless an equal value is stored; returns true if inserted	O(log n)	O(h)
getOrInsert(value)	The stored equal value, inserting value first if there is none	O(log n)	O(h)
delete(value)	Removes the equal value; returns true if removed	O(log n)	O(h)
clear()	Removes all values	O(1)	O(1)
min(), max()	The smallest / largest value, or undefined	O(log n)	O(h)
popMin(), popMax()	Removes and returns the smallest / largest value	O(log n)	O(h)
floor(value), ceil(value)	The greatest value <= / least value >= value	O(log n)	O(h)
lower(value), higher(value)	The greatest value < / least value > value	O(log n)	O(h)
values(), [Symbol.iterator]()	Iterates in ascending order	O(n)	O(n)
valuesReversed()	Iterates in descending order	O(n)	O(n)
range({ gt, gte, lt, lte, reverse })	Iterates over the values within the bounds	O(log n + k)	O(h + k)
forEach(callback, thisArg?)	Calls callback(value, index, tree) in ascending order	O(n)	O(n)
toArray()	The values in ascending order	O(n)	O(n)

h is the height of a BSTree: about log n for random insertion orders, up to n for sorted ones, and growing towards √n under many random removals and insertions. k is the number of values in a range.

Iteration

Iteration always follows the comparator order. Iterators are iterable themselves, and on Node.js they support the iterator helpers:

import { AVLTree } from "bstrees";

const tree = AVLTree.from([1, 2, 3, 4, 5, 6]);

[...tree]; // [1, 2, 3, 4, 5, 6]
[...tree.valuesReversed()]; // [6, 5, 4, 3, 2, 1]
[...tree.range({ gt: 2, lte: 5 })]; // [3, 4, 5]
[...tree.range({ lt: 3, reverse: true })]; // [2, 1]
tree
  .values()
  .filter((value) => value % 2 === 0)
  .take(2)
  .toArray(); // [2, 4]
Copy

A range bound that is missing or undefined leaves that side open. Passing both gt and gte, or both lt and lte, throws a TypeError.

Modifying the tree while iterating is allowed and does not invalidate iterators. An iterator remembers the last value it returned. After the tree changes, it continues with the first value past that one that is currently stored:

• removed values are skipped;
• values inserted ahead of the iterator are visited;
• values inserted behind it are not;
• no value is visited twice.

This differs from a Set, whose iterators follow the insertion order: a value that is deleted and added again, or added after clear(), is visited by a Set iterator again, but not by a tree iterator that has already passed it.

Because an iterator finds its place again by comparing with the last value it returned, do not change the fields the comparator reads of that value while you still use the iterator, even after removing the value from the tree. For example, after tree.delete(value) keep value.id as it is until the iterator has moved past it or you stop using it.

import { AVLTree } from "bstrees";

const tree = AVLTree.from([1, 2, 3, 4, 5]);

for (const value of tree) {
  if (value % 2 === 1) {
    tree.delete(value + 1);
  }
}

tree.toArray(); // [1, 3, 5]
Copy

Benchmarks

Scenario	n	AVLTree	BSTree	sorted array	Set
insert (random order)	1,000	0.19 ms ±0%	0.20 ms ±0%	0.19 ms ±0%	0.019 ms ±0%
insert (random order)	10,000	2.6 ms ±1%	2.8 ms ±0%	6.1 ms ±0%	0.41 ms ±0%
insert (random order)	100,000	35 ms ±1%	40 ms ±2%	602 ms ±15%	4.8 ms ±2%
insert (sorted order)	1,000	0.17 ms ±1%	10 ms ±0%	0.12 ms ±0%	0.019 ms ±0%
insert (sorted order)	10,000	2.0 ms ±1%	1104 ms ±7%	1.7 ms ±4%	0.44 ms ±2%
insert (sorted order)	100,000	23 ms ±2%	—	18 ms ±0%	4.8 ms ±1%
has (every value)	1,000	0.12 ms ±0%	0.14 ms ±0%	0.056 ms ±3%	0.0062 ms ±0%
has (every value)	10,000	1.7 ms ±1%	2.1 ms ±1%	2.3 ms ±0%	0.17 ms ±0%
has (every value)	100,000	27 ms ±2%	34 ms ±5%	32 ms ±0%	2.5 ms ±1%
delete (every value)	1,000	0.19 ms ±1%	0.18 ms ±3%	0.20 ms ±1%	0.017 ms ±1%
delete (every value)	10,000	2.8 ms ±8%	2.6 ms ±1%	6.1 ms ±1%	0.35 ms ±1%
delete (every value)	100,000	38 ms ±2%	42 ms ±2%	635 ms ±20%	4.4 ms ±3%
iterate in order	1,000	0.037 ms ±1%	0.039 ms ±1%	0.012 ms ±12%	—
iterate in order	10,000	0.36 ms ±0%	0.40 ms ±1%	0.10 ms ±0%	—
iterate in order	100,000	3.7 ms ±0%	4.1 ms ±0%	1.2 ms ±0%	—
range (1000 × 100 values)	1,000	4.7 ms ±1%	4.8 ms ±0%	0.25 ms ±0%	—
range (1000 × 100 values)	10,000	4.9 ms ±4%	5.3 ms ±1%	0.30 ms ±1%	—
range (1000 × 100 values)	100,000	5.5 ms ±1%	6.6 ms ±2%	0.36 ms ±1%	—
popMin (until empty)	1,000	0.069 ms ±1%	0.048 ms ±0%	0.034 ms ±1%	—
popMin (until empty)	10,000	0.77 ms ±0%	0.67 ms ±1%	0.36 ms ±2%	—
popMin (until empty)	100,000	11 ms ±4%	9.5 ms ±3%	1209 ms ±4%	—

Mean time per task and its relative margin of error (95% confidence), measured with npm run bench on an Apple M1 Pro with Node.js 26.11. Treat the numbers as indicative: they vary between runs and machines, and garbage collection makes the n = 100 000 rows noisier. Run npm run bench to measure on your machine.

The sorted array uses binary search and splice, and its popMin uses shift(), which is O(n). Set is an unordered baseline. — marks skipped benchmarks: Set does not support the ordered scenarios, and a BSTree that receives 100 000 sorted values degrades into a list and takes over a minute.

Upgrading

Version 4 changes only the license, to MIT; the API is the same as in 3.x. Version 3 replaced the node-based API of 2.x with the value-based API above. See MIGRATION.md.

License

MIT