Product
Introducing License Enforcement in Socket
Ensure open-source compliance with Socket’s License Enforcement Beta. Set up your License Policy and secure your software!
By Philipp Burckhardt - Oct 17, 2024
bst-typed
Advanced tools
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
npm
npm i bst-typed --save
yarn
yarn add bst-typed
methods
snippet
TS
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
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
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
bst
| 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 |
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. |
FAQs
BST (Binary Search Tree). Javascript & Typescript Data Structure.
The npm package bst-typed receives a total of 160 weekly downloads. As such, bst-typed popularity was classified as not popular.
We found that bst-typed demonstrated a healthy version release cadence and project activity because the last version was released less than a year ago. It has 0 open source maintainers collaborating on the project.
Package last updated on 10 Oct 2024
Did you know?
Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.
Related posts
Product
Enhancing Open-Source Compliance: Introducing Socket’s Advanced License Analysis
We're launching a new set of license analysis and compliance features for analyzing, managing, and complying with licenses across a range of supported languages and ecosystems.
By Christopher Bailey - Oct 17, 2024
Product
Introducing Socket Optimize
We're excited to introduce Socket Optimize, a powerful CLI command to secure open source dependencies with tested, optimized package overrides.
By John-David Dalton - Oct 16, 2024