bst-typed
Advanced tools
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
npm i bst-typed
yarn add bst-typed
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
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
| Data Structure | Unit Test | Performance Test | API Documentation | Implemented |
|---|---|---|---|---|
| Binary Tree | 
|
| Binary Tree | |
| Binary Search Tree (BST) | | | BST | |
| AVL Tree | | | AVLTree | |
| Tree Multiset | | | TreeMultiset | |
| Segment Tree | SegmentTree | | ||
| Binary Indexed Tree | | BinaryIndexedTree | | |
| Graph | | | AbstractGraph | |
| Directed Graph | | | DirectedGraph | |
| Undirected Graph | | | UndirectedGraph | |
| Linked List | | | SinglyLinkedList | |
| Singly Linked List | | | SinglyLinkedList | |
| Doubly Linked List | | | DoublyLinkedList | |
| Queue | | | Queue | |
| Object Deque | | | ObjectDeque | |
| Array Deque | | | ArrayDeque | |
| Stack | | Stack | | |
| Coordinate Set | CoordinateSet | | ||
| Coordinate Map | CoordinateMap | | ||
| Heap | | | Heap | |
| Priority Queue | | | PriorityQueue | |
| Max Priority Queue | | | MaxPriorityQueue | |
| Min Priority Queue | | | MinPriorityQueue | |
| Trie | | Trie | |
| Big O Notation | Type | Computations for 10 elements | Computations for 100 elements | Computations for 1000 elements |
|---|---|---|---|---|
| O(1) | Constant | 1 | 1 | 1 |
| O(log N) | Logarithmic | 3 | 6 | 9 |
| O(N) | Linear | 10 | 100 | 1000 |
| O(N log N) | n log(n) | 30 | 600 | 9000 |
| O(N^2) | Quadratic | 100 | 10000 | 1000000 |
| O(2^N) | Exponential | 1024 | 1.26e+29 | 1.07e+301 |
| O(N!) | Factorial | 3628800 | 9.3e+157 | 4.02e+2567 |
| Data Structure | Access | Search | Insertion | Deletion | Comments |
|---|---|---|---|---|---|
| Array | 1 | n | n | n | |
| Stack | n | n | 1 | 1 | |
| Queue | n | n | 1 | 1 | |
| Linked List | n | n | 1 | n | |
| Hash Table | - | n | n | n | In case of perfect hash function costs would be O(1) |
| Binary Search Tree | n | n | n | n | In case of balanced tree costs would be O(log(n)) |
| B-Tree | log(n) | log(n) | log(n) | log(n) | |
| Red-Black Tree | log(n) | log(n) | log(n) | log(n) | |
| AVL Tree | log(n) | log(n) | log(n) | log(n) | |
| Bloom Filter | - | 1 | 1 | - | False positives are possible while searching |
| Name | Best | Average | Worst | Memory | Stable | Comments |
|---|---|---|---|---|---|---|
| Bubble sort | n | n2 | n2 | 1 | Yes | |
| Insertion sort | n | n2 | n2 | 1 | Yes | |
| Selection sort | n2 | n2 | n2 | 1 | No | |
| Heap sort | n log(n) | n log(n) | n log(n) | 1 | No | |
| Merge sort | n log(n) | n log(n) | n log(n) | n | Yes | |
| Quick sort | n log(n) | n log(n) | n2 | log(n) | No | Quicksort is usually done in-place with O(log(n)) stack space |
| Shell sort | n log(n) | depends on gap sequence | n (log(n))2 | 1 | No | |
| Counting sort | n + r | n + r | n + r | n + r | Yes | r - biggest number in array |
| Radix sort | n * k | n * k | n * k | n + k | Yes | k - length of longest key |
FAQs
BST (Binary Search Tree). Javascript & Typescript Data Structure.
The npm package bst-typed receives a total of 837 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.
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.
Security News
Research
A malicious npm package disguised as a WhatsApp client is exploiting authentication flows with a remote kill switch to exfiltrate data and destroy files.
Security News
PyPI now supports digital attestations, enhancing security and trust by allowing package maintainers to verify the authenticity of Python packages.
Security News
GitHub removed 27 malicious pull requests attempting to inject harmful code across multiple open source repositories, in another round of low-effort attacks.