An unbalanced binary search tree. The values are in ascending order by default, using JavaScript's built-in comparison operators to sort the values.
For performance, it's recommended that you use a self-balancing binary search tree instead of this one unless you are extending this to create a self-balancing tree. See RedBlackTree for an example of how BinarySearchTree can be extended to create a self-balancing binary search tree.
| Method | Average Case | Worst Case |
|---|---|---|
| find(value) | O(log n) | O(n) |
| insert(value) | O(log n) | O(n) |
| remove(value) | O(log n) | O(n) |
| min() | O(log n) | O(n) |
| max() | O(log n) | O(n) |
Example 1
Example 1
import { BinarySearchTree, ascend, descend, } from "@std/data-structures"; import { assertEquals } from "@std/assert/assert-equals"; const values = [3, 10, 13, 4, 6, 7, 1, 14]; const tree = new BinarySearchTree<number>(); values.forEach((value) => tree.insert(value)); assertEquals([...tree], [1, 3, 4, 6, 7, 10, 13, 14]); assertEquals(tree.min(), 1); assertEquals(tree.max(), 14); assertEquals(tree.find(42), null); assertEquals(tree.find(7), 7); assertEquals(tree.remove(42), false); assertEquals(tree.remove(7), true); assertEquals([...tree], [1, 3, 4, 6, 10, 13, 14]); const invertedTree = new BinarySearchTree<number>(descend); values.forEach((value) => invertedTree.insert(value)); assertEquals([...invertedTree], [14, 13, 10, 7, 6, 4, 3, 1]); assertEquals(invertedTree.min(), 14); assertEquals(invertedTree.max(), 1); assertEquals(invertedTree.find(42), null); assertEquals(invertedTree.find(7), 7); assertEquals(invertedTree.remove(42), false); assertEquals(invertedTree.remove(7), true); assertEquals([...invertedTree], [14, 13, 10, 6, 4, 3, 1]); const words = new BinarySearchTree<string>((a, b) => ascend(a.length, b.length) || ascend(a, b) ); ["truck", "car", "helicopter", "tank", "train", "suv", "semi", "van"] .forEach((value) => words.insert(value)); assertEquals([...words], [ "car", "suv", "van", "semi", "tank", "train", "truck", "helicopter", ]); assertEquals(words.min(), "car"); assertEquals(words.max(), "helicopter"); assertEquals(words.find("scooter"), null); assertEquals(words.find("tank"), "tank"); assertEquals(words.remove("scooter"), false); assertEquals(words.remove("tank"), true); assertEquals([...words], [ "car", "suv", "van", "semi", "train", "truck", "helicopter", ]);
[Symbol.iterator](): IterableIterator<T>
Create an iterator over this tree that traverses the tree in-order (LNR, Left-Node-Right).
clear(): void
Remove all values from the binary search tree.
The complexity of this operation is O(1).
Check if a value exists in the binary search tree.
The complexity of this operation depends on the underlying structure of the tree. Refer to the documentation of the structure itself for more details.
Add a value to the binary search tree if it does not already exist in the tree.
The complexity of this operation is on average O(log n), where n is the number of values in the tree. In the worst case, the complexity is O(n).
insertNode(Node: BinarySearchNode,value: T,): BinarySearchNode<T> | null
Check if the binary search tree is empty.
The complexity of this operation is O(1).
Create an iterator over this tree that traverses the tree in-order (LNR, Left-Node-Right).
Create an iterator over this tree that traverses the tree in post-order (LRN, Left-Right-Node).
Create an iterator over this tree that traverses the tree in level-order (BFS, Breadth-First Search).
Retrieve the highest (right most) value in the binary search tree, or null if the tree is empty.
The complexity of this operation depends on the underlying structure of the tree. Refer to the documentation of the structure itself for more details.
Retrieve the lowest (left most) value in the binary search tree, or null if the tree is empty.
The complexity of this operation depends on the underlying structure of the tree. Refer to the documentation of the structure itself for more details.
Create an iterator over this tree that traverses the tree in pre-order (NLR, Node-Left-Right).
Remove a value from the binary search tree if it exists in the tree.
The complexity of this operation is on average O(log n), where n is the number of values in the tree. In the worst case, the complexity is O(n).
removeNode(node: BinarySearchNode<T>): BinarySearchNode<T> | null
Removes the given node, and returns the node that was physically removed from the tree.
Create an iterator over this tree that traverses the tree in reverse in-order (RNL, Right-Node-Left).
rotateNode(node: BinarySearchNode<T>,direction: Direction,): void
from<T>(collection: ,): BinarySearchTree<T>
Creates a new binary search tree from an array like, an iterable object, or an existing binary search tree.
A custom comparison function can be provided to sort the values in a specific order. By default, the values are sorted in ascending order, unless a BinarySearchTree is passed, in which case the comparison function is copied from the input tree.
from<T,U,V = undefined,>(collection: ,): BinarySearchTree<U>
Create a new binary search tree from an array like, an iterable object, or an existing binary search tree.
A custom mapping function can be provided to transform the values before inserting them into the tree.
A custom comparison function can be provided to sort the values in a specific order. A custom mapping function can be provided to transform the values before inserting them into the tree. By default, the values are sorted in ascending order, unless a BinarySearchTree is passed, in which case the comparison function is copied from the input tree. The comparison operator is used to sort the values in the tree after mapping the values.