| test name | time taken (ms) | executions per sec | sample deviation |
|---|---|---|---|
| 10,000 add randomly | 31.59 | 31.66 | 2.74e-4 |
| 10,000 add & delete randomly | 74.56 | 13.41 | 8.32e-4 |
| 10,000 addMany | 29.16 | 34.30 | 0.00 |
| 10,000 get | 29.24 | 34.21 | 0.00 |
bst-typed
v2.2.8TypeScript
Binary Search Tree
bst data structurebinary search tree data structurebstBSTbinary search treebinarysearchtreeBinary Search Treebinary-search-treejavascriptjava script
0/weekUpdated 1 weeks agoMITUnpacked: 4.4 MB
Published by Pablo Zeng zrwusa@gmail.com
npm install bst-typed!NPM
!GitHub top language
!npm
!eslint
!npm bundle size
!npm bundle size
!npm
What
Brief
This is a standalone BST (Binary Search Tree) data structure from the data-structure-typed collection. If you wish to
access more data structures or advanced features, you can transition to directly installing the
complete data-structure-typed package
How
install
$3
``bash`
npm i bst-typed --save
$3
`bash`
yarn add bst-typed
$3
#### TS
`typescript
import {BST, BSTNode} from 'data-structure-typed';
// / or if you prefer / import {BST, BSTNode} from 'bst-typed';
const bst = new BST();
bst instanceof BST; // true
bst.add(11);
bst.add(3);
const idsAndValues = [15, 1, 8, 13, 16, 2, 6, 9, 12, 14, 4, 7, 10, 5];
bst.addMany(idsAndValues);
bst.root instanceof BSTNode; // true
if (bst.root) bst.root.id; // 11
bst.size; // 16
bst.has(6); // true
const node6 = bst.get(6);
node6 && bst.getHeight(6); // 2
node6 && bst.getDepth(6); // 3
const nodeId10 = bst.get(10);
nodeId10?.id; // 10
const nodeVal9 = bst.get(9, 'val');
nodeVal9?.id; // 9
const leftMost = bst.getLeftMost();
leftMost?.id; // 1
const node15 = bst.get(15);
const minNodeBySpecificNode = node15 && bst.getLeftMost(node15);
minNodeBySpecificNode?.id; // 12
const subTreeSum = node15 && bst.subTreeSum(15);
subTreeSum; // 70
const lesserSum = bst.lesserSum(10);
lesserSum; // 45
node15 instanceof BSTNode; // true
const node11 = bst.get(11);
node11 instanceof BSTNode; // true
const dfsInorderNodes = bst.DFS('in', 'node');
dfsInorderNodes[0].id; // 1
dfsInorderNodes[dfsInorderNodes.length - 1].id; // 16
bst.perfectlyBalance();
bst.isPerfectlyBalanced(); // true
const bfsNodesAfterBalanced = bst.BFS('node');
bfsNodesAfterBalanced[0].id; // 8);
bfsNodesAfterBalanced[bfsNodesAfterBalanced.length - 1].id; // 16
const removed11 = bst.remove(11, true);
removed11 instanceof Array; // true
if (removed11[0].deleted) removed11[0].deleted.id; // 11
bst.isAVLBalanced(); // true
bst.getHeight(15); // 1
const removed1 = bst.remove(1, true);
removed1 instanceof Array; // true
if (removed1[0].deleted) removed1[0].deleted.id; // 1
bst.isAVLBalanced(); // true
bst.getHeight(); // 4
const removed4 = bst.remove(4, true);
removed4 instanceof Array; // true
if (removed4[0].deleted) removed4[0].deleted.id; // 4
bst.isAVLBalanced(); // true
bst.getHeight(); // 4
const removed10 = bst.remove(10, true);
if (removed10[0].deleted) removed10[0].deleted.id; // 10
bst.isAVLBalanced(); // false
bst.getHeight(); // 4
const removed15 = bst.remove(15, true);
if (removed15[0].deleted) removed15[0].deleted.id; // 15
bst.isAVLBalanced(); // true
bst.getHeight(); // 3
const removed5 = bst.remove(5, true);
if (removed5[0].deleted) removed5[0].deleted.id; // 5
bst.isAVLBalanced(); // true
bst.getHeight(); // 3
const removed13 = bst.remove(13, true);
if (removed13[0].deleted) removed13[0].deleted.id; // 13
bst.isAVLBalanced(); // true
bst.getHeight(); // 3
const removed3 = bst.remove(3, true);
if (removed3[0].deleted) removed3[0].deleted.id; // 3
bst.isAVLBalanced(); // false
bst.getHeight(); // 3
const removed8 = bst.remove(8, true);
if (removed8[0].deleted) removed8[0].deleted.id; // 8
bst.isAVLBalanced(); // true
bst.getHeight(); // 3
const removed6 = bst.remove(6, true);
if (removed6[0].deleted) removed6[0].deleted.id; // 6
bst.remove(6, true).length; // 0
bst.isAVLBalanced(); // false
bst.getHeight(); // 3
const removed7 = bst.remove(7, true);
if (removed7[0].deleted) removed7[0].deleted.id; // 7
bst.isAVLBalanced(); // false
bst.getHeight(); // 3
const removed9 = bst.remove(9, true);
if (removed9[0].deleted) removed9[0].deleted.id; // 9
bst.isAVLBalanced(); // false
bst.getHeight(); // 3
const removed14 = bst.remove(14, true);
if (removed14[0].deleted) removed14[0].deleted.id; // 14
bst.isAVLBalanced(); // false
bst.getHeight(); // 2
bst.isAVLBalanced(); // false
const bfsIDs = bst.BFS();
bfsIDs[0]; // 2
bfsIDs[1]; // 12
bfsIDs[2]; // 16
const bfsNodes = bst.BFS('node');
bfsNodes[0].id; // 2
bfsNodes[1].id; // 12
bfsNodes[2].id; // 16
`
#### JS
`javascript
const {BST, BSTNode} = require('data-structure-typed');
// / or if you prefer / const {BST, BSTNode} = require('bst-typed');
const bst = new BST();
bst instanceof BST; // true
bst.add(11);
bst.add(3);
const idsAndValues = [15, 1, 8, 13, 16, 2, 6, 9, 12, 14, 4, 7, 10, 5];
bst.addMany(idsAndValues);
bst.root instanceof BSTNode; // true
if (bst.root) bst.root.id; // 11
bst.size; // 16
bst.has(6); // true
const node6 = bst.get(6);
node6 && bst.getHeight(6); // 2
node6 && bst.getDepth(6); // 3
const nodeId10 = bst.get(10);
nodeId10?.id; // 10
const nodeVal9 = bst.get(9, 'val');
nodeVal9?.id; // 9
const leftMost = bst.getLeftMost();
leftMost?.id; // 1
const node15 = bst.get(15);
const minNodeBySpecificNode = node15 && bst.getLeftMost(node15);
minNodeBySpecificNode?.id; // 12
const subTreeSum = node15 && bst.subTreeSum(15);
subTreeSum; // 70
const lesserSum = bst.lesserSum(10);
lesserSum; // 45
node15 instanceof BSTNode; // true
const node11 = bst.get(11);
node11 instanceof BSTNode; // true
const dfsInorderNodes = bst.DFS('in', 'node');
dfsInorderNodes[0].id; // 1
dfsInorderNodes[dfsInorderNodes.length - 1].id; // 16
bst.perfectlyBalance();
bst.isPerfectlyBalanced(); // true
const bfsNodesAfterBalanced = bst.BFS('node');
bfsNodesAfterBalanced[0].id; // 8);
bfsNodesAfterBalanced[bfsNodesAfterBalanced.length - 1].id; // 16
const removed11 = bst.remove(11, true);
removed11 instanceof Array; // true
if (removed11[0].deleted) removed11[0].deleted.id; // 11
bst.isAVLBalanced(); // true
bst.getHeight(15); // 1
const removed1 = bst.remove(1, true);
removed1 instanceof Array; // true
if (removed1[0].deleted) removed1[0].deleted.id; // 1
bst.isAVLBalanced(); // true
bst.getHeight(); // 4
const removed4 = bst.remove(4, true);
removed4 instanceof Array; // true
if (removed4[0].deleted) removed4[0].deleted.id; // 4
bst.isAVLBalanced(); // true
bst.getHeight(); // 4
const removed10 = bst.remove(10, true);
if (removed10[0].deleted) removed10[0].deleted.id; // 10
bst.isAVLBalanced(); // false
bst.getHeight(); // 4
const removed15 = bst.remove(15, true);
if (removed15[0].deleted) removed15[0].deleted.id; // 15
bst.isAVLBalanced(); // true
bst.getHeight(); // 3
const removed5 = bst.remove(5, true);
if (removed5[0].deleted) removed5[0].deleted.id; // 5
bst.isAVLBalanced(); // true
bst.getHeight(); // 3
const removed13 = bst.remove(13, true);
if (removed13[0].deleted) removed13[0].deleted.id; // 13
bst.isAVLBalanced(); // true
bst.getHeight(); // 3
const removed3 = bst.remove(3, true);
if (removed3[0].deleted) removed3[0].deleted.id; // 3
bst.isAVLBalanced(); // false
bst.getHeight(); // 3
const removed8 = bst.remove(8, true);
if (removed8[0].deleted) removed8[0].deleted.id; // 8
bst.isAVLBalanced(); // true
bst.getHeight(); // 3
const removed6 = bst.remove(6, true);
if (removed6[0].deleted) removed6[0].deleted.id; // 6
bst.remove(6, true).length; // 0
bst.isAVLBalanced(); // false
bst.getHeight(); // 3
const removed7 = bst.remove(7, true);
if (removed7[0].deleted) removed7[0].deleted.id; // 7
bst.isAVLBalanced(); // false
bst.getHeight(); // 3
const removed9 = bst.remove(9, true);
if (removed9[0].deleted) removed9[0].deleted.id; // 9
bst.isAVLBalanced(); // false
bst.getHeight(); // 3
const removed14 = bst.remove(14, true);
if (removed14[0].deleted) removed14[0].deleted.id; // 14
bst.isAVLBalanced(); // false
bst.getHeight(); // 2
bst.isAVLBalanced(); // false
const bfsIDs = bst.BFS();
bfsIDs[0]; // 2
bfsIDs[1]; // 12
bfsIDs[2]; // 16
const bfsNodes = bst.BFS('node');
bfsNodes[0].id; // 2
bfsNodes[1].id; // 12
bfsNodes[2].id; // 16
`
[//]: # (No deletion!!! Start of Example Replace Section)
$3
`
typescript
// Create a simple BST with numeric keys
const bst = new BST([11, 3, 15, 1, 8, 13, 16, 2, 6, 9, 12, 14, 4, 7, 10, 5]); bst.print();
// _______8__________
// / \
// ___4___ ____12_____
// / \ / \
// _2_ _6_ _10__ _14__
// / \ / \ / \ / \
// 1 3 5 7 9 11 13 15__
// \
// 16
// Verify size
console.log(bst.size); // 16;
// Add new elements
bst.set(17);
bst.set(0);
console.log(bst.size); // 18;
// Verify keys are searchable
console.log(bst.has(11)); // true;
console.log(bst.has(100)); // false;
`$3
typescript
const bst = new BST([11, 3, 15, 1, 8, 13, 16, 2, 6, 9, 12, 14, 4, 7, 10, 5]); // Delete a leaf node
bst.delete(1);
console.log(bst.has(1)); // false;
// Delete a node with one child
bst.delete(2);
console.log(bst.has(2)); // false;
// Delete a node with two children
bst.delete(3);
console.log(bst.has(3)); // false;
// Size decreases with each deletion
console.log(bst.size); // 13;
// Other nodes remain searchable
console.log(bst.has(11)); // true;
console.log(bst.has(15)); // true;
`$3
typescript
const dataset1 = new BST([
[1, 'A'],
[7, 'G']
]);
const dataset2 = [
[2, 'B'],
[6, 'F']
];
const dataset3 = new BST([
[3, 'C'],
[5, 'E'],
[4, 'D']
]); // Merge datasets into a single BinarySearchTree
const merged = new BST(dataset1);
merged.setMany(dataset2);
merged.merge(dataset3);
// Verify merged dataset is in sorted order
console.log([...merged.values()]); // ['A', 'B', 'C', 'D', 'E', 'F', 'G'];
`$3
typescript
interface Expression {
id: number;
operator: string;
precedence: number;
} // BST efficiently stores and retrieves operators by precedence
const operatorTree = new BST(
[
[1, { id: 1, operator: '+', precedence: 1 }],
[2, { id: 2, operator: '*', precedence: 2 }],
[3, { id: 3, operator: '/', precedence: 2 }],
[4, { id: 4, operator: '-', precedence: 1 }],
[5, { id: 5, operator: '^', precedence: 3 }]
],
{ isMapMode: false }
);
console.log(operatorTree.size); // 5;
// Quick lookup of operators
const mult = operatorTree.get(2);
console.log(mult?.operator); // '*';
console.log(mult?.precedence); // 2;
// Check if operator exists
console.log(operatorTree.has(5)); // true;
console.log(operatorTree.has(99)); // false;
// Retrieve operator by precedence level
const expNode = operatorTree.getNode(3);
console.log(expNode?.key); // 3;
console.log(expNode?.value?.precedence); // 2;
// Delete operator and verify
operatorTree.delete(1);
console.log(operatorTree.has(1)); // false;
console.log(operatorTree.size); // 4;
// Get tree height for optimization analysis
const treeHeight = operatorTree.getHeight();
console.log(treeHeight); // > 0;
// Remaining operators are still accessible
const remaining = operatorTree.get(2);
console.log(remaining); // defined;
`$3
typescript
const bst = new BST([20, 10, 30, 5, 15, 25, 35, 3, 7, 12, 18]); // LCA helper function
const findLCA = (num1: number, num2: number): number | undefined => {
const path1 = bst.getPathToRoot(num1);
const path2 = bst.getPathToRoot(num2);
// Find the first common ancestor
return findFirstCommon(path1, path2);
};
function findFirstCommon(arr1: (number | undefined)[], arr2: (number | undefined)[]): number | undefined {
for (const num of arr1) {
if (arr2.indexOf(num) !== -1) {
return num;
}
}
return undefined;
}
// Assertions
console.log(findLCA(3, 10)); // 7;
console.log(findLCA(5, 35)); // 15;
console.log(findLCA(20, 30)); // 25;
``[//]: # (No deletion!!! End of Example Replace Section)
API docs & Examples
Data Structures
| Data Structure | Unit Test | Performance Test | API Docs |
|---|---|---|---|
| Binary Search Tree (BST) |  | | BST |
Standard library data structure comparison
| Data Structure Typed | C++ STL | java.util | Python collections |
|---|---|---|---|
| BST<K, V> | - | - | - |
Benchmark
[//]: # (No deletion!!! Start of Replace Section)
bst
[//]: # (No deletion!!! End of Replace Section)
Built-in classic algorithms
| Algorithm | Function Description | Iteration Type |
|---|---|---|
| Binary Tree DFS | Traverse a binary tree in a depth-first manner, starting from the root node, first visiting the left subtree, and then the right subtree, using recursion. | Recursion + Iteration |
| Binary Tree BFS | Traverse a binary tree in a breadth-first manner, starting from the root node, visiting nodes level by level from left to right. | Iteration |
| Binary Tree Morris | Morris traversal is an in-order traversal algorithm for binary trees with O(1) space complexity. It allows tree traversal without additional stack or recursion. | Iteration |
Software Engineering Design Standards
| Principle | Description |
|---|---|
| Practicality | Follows ES6 and ESNext standards, offering unified and considerate optional parameters, and simplifies method names. |
| Extensibility | Adheres to OOP (Object-Oriented Programming) principles, allowing inheritance for all data structures. |
| Modularization | Includes data structure modularization and independent NPM packages. |
| Efficiency | All methods provide time and space complexity, comparable to native JS performance. |
| Maintainability | Follows open-source community development standards, complete documentation, continuous integration, and adheres to TDD (Test-Driven Development) patterns. |
| Testability | Automated and customized unit testing, performance testing, and integration testing. |
| Portability | Plans for porting to Java, Python, and C++, currently achieved to 80%. |
| Reusability | Fully decoupled, minimized side effects, and adheres to OOP. |
| Security | Carefully designed security for member variables and methods. Read-write separation. Data structure software does not need to consider other security aspects. |
| Scalability | Data structure software does not involve load issues. |