bst-typed v2.0.3

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

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

Merge 3 sorted datasets

    const dataset1 = new BST<number, string>([
      [1, 'A'],
      [7, 'G']
    ]);
    const dataset2 = [
      [2, 'B'],
      [6, 'F']
    ];
    const dataset3 = new BST<number, string>([
      [3, 'C'],
      [5, 'E'],
      [4, 'D']
    ]);

    // Merge datasets into a single BinarySearchTree
    const merged = new BST<number, string>(dataset1);
    merged.addMany(dataset2);
    merged.merge(dataset3);

    // Verify merged dataset is in sorted order
    console.log([...merged.values()]); // ['A', 'B', 'C', 'D', 'E', 'F', 'G']

Find elements in a range

    const bst = new BST<number>([10, 5, 15, 3, 7, 12, 18]);
    console.log(bst.search(new Range(5, 10))); // [5, 7, 10]
    console.log(bst.rangeSearch([4, 12], node => node.key.toString())); // ['5', '7', '10', '12']
    console.log(bst.search(new Range(4, 12, true, false))); // [5, 7, 10]
    console.log(bst.rangeSearch([15, 20])); // [15, 18]
    console.log(bst.search(new Range(15, 20, false))); // [18]

Find lowest common ancestor

    const bst = new BST<number>([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[], arr2: number[]): 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

API docs & Examples

API Docs

Live Examples

Examples Repository

Data Structures

Standard library data structure comparison

Benchmark

Built-in classic algorithms

Software Engineering Design Standards