✌️🔍🌳 binary-search-tree

A zero-dependency TypeScript library to work with binary search trees and arrays of any types, with a functional-programming and immutable approach.

Table of Content

• ✌️🔍🌳 binary-search-tree
  • Table of Content
  • Installation
  • Usage
  • Documentation
    • toBST
    • balance, isBalanced, getBalance
    • add
    • remove
    • find, findFromPath
    • findLowestAncestor
    • find(Gt/Gte/Lt/Lte)
    • find(Min/Max)(Height), count
    • getDistanceBetweenNodes
    • traverse
    • toArray
    • isLeaf, isBranch
    • hasLeft, hasRight
    • makeCompareUtils
    • The infamous BinarySearchTree class

Installation

yarn add @romainfieve/binary-search-tree

or

npm install @romainfieve/binary-search-tree

Usage

type Hero = { name: string };

const compareAlpha = (a: Hero, b: Hero) => a.name.localeCompare(b.name);

const addAlpha = makeAdd(compareAlpha);
const removeAlpha = makeRemove(compareAlpha);
const findAlpha = makeFind(compareAlpha);

const heroes: Hero[] = [
    { name: 'Han' },
    { name: 'Anakin' },
    { name: 'Leia' },
    { name: 'Luke' },
    { name: 'Padme' },
    { name: 'Lando' },
    { name: 'Chewie' },
];
const unbalancedTree = toBST(heroes, compareAlpha, { isBalanced: false });

const updatedTree = pipe(
    (t) => addAlpha(t, { name: 'Yoda' }),
    (t) => addAlpha(t, { name: 'Obiwan' }),
    (t) => addAlpha(t, [{ name: 'Boba' }, { name: 'Grogu' }]),
    (t) => removeAlpha(t, [{ name: 'Han' }, { name: 'Padme' }]),
    (t) => removeAlpha(t, { name: 'Luke' })
)(unbalancedTree);

// unbalancedTree:                             | Schema of "unbalancedTree"
//                                             |
// {                                           |             Han
//     data: [{ name: 'Han' }],                |           /     \
//     left: {                                 |     Anakin       Leia
//         data: [{ name: 'Anakin' }],         |           \     /    \
//         right: {                            |       Chewie  Lando   Luke
//             data : [{ name: 'Chewie' }],    |                         \
//         },                                  |                        Padme
//     },                                      |
//     right: {                                | Schema of "updatedTree"
//         data: [{ name: 'Leia' }],           |
//         left: {                             |            Lando
//             data: [{ name: 'Lando' }],      |           /     \
//         },                                  |     Anakin       Leia
//         right: {                            |         \            \
//             data: [{ name: 'Luke' }],       |       Chewie        Obiwan
//             right: {                        |        /    \            \
//                 data : [{ name: 'Padme' }], |      Boba  Grogu        Yoda
//             },                              |
//         },                                  |
//     },                                      |
// };                                          |

const min = findMin(updatedTree).data[0].name; // Anakin
const max = findMax(updatedTree).data[0].name; // Yoda
const grogu = findAlpha(updatedTree, { name: 'Grogu' }).node.data[0].name; // Grogu
const groguPath = findAlpha(updatedTree, { name: 'Grogu' }).path; // ['left', 'right', 'right']
// Thanks to the compare function, the search will traverse like this:
// Lando -> Anakin -> Chewie -> Grogu

Documentation

toBST

Converts the given array to a balanced binary search tree (toBST), depending on a given compare function.

:warning: For obvious performance reasons, toBST will create a BALANCED binary search tree by default. Whilst passing the option { isBalanced: false } will indeed respect the order of the source array for insertion, beware that performace will be greatly impacted. Worst, if you pass an array presorted with the compare function, the BST will be linear, and the Big O notation will be n!.

const arr = [10, 32, 13, 2, 89, 5, 50];
const compare = (a: number, b: number) => a - b;

const tree = toBST(arr, compare);
// or
const unbalancedTree = toBST(arr, compare, { isBalanced: false });

// Schema of "tree"         |    "unbalancedTree"
//                          |
//           13             |          10
//        /     \           |       /     \
//       5      50          |      2      32
//     /  \    /  \         |       \    /  \
//    2   10  32   89       |        5  13  89
//                          |               /
//                          |             50

balance, isBalanced, getBalance

Balances the given binary search tree with the given compare function and returns a new tree, without modifing the original tree in place.

:warning: Using another compare function than the one used to create the tree with toBST will of course f**k up the tree. A safer approach consists of using makeBalance. It curries a balance closure function with the given compare function.

getBalance(unbalancedTree); // 2
isBalanced(unbalancedTree); // false

const tree = balance(unbalancedTree, compare);
// or
const safeBalance = makeBalance(compare);
const tree = safeBalance(unbalancedTree);

getBalance(tree); // 0
isBalanced(tree); // true

// Schema of "unbalancedTree"  =>        "tree"
//                             |
//       10                    |            13
//    /     \                  |         /     \
//   2      32                 |        5      50
//    \    /  \                |      /  \    /  \
//     5  13  89               |     2   10  32   89
//            /                |
//          50                 |

add

Adds a (or list of) given node(s) to the given binary search tree with the given compare function and returns a new tree, without modifing the original tree in place.

:warning: Using another compare function than the one used to create the tree with toBST will of course f**k up the tree. A safer approach consists of using makeAdd. It curries an add closure function with the given compare function.

const modifiedTree = add(tree, compare, 11);
const reModifiedTree = add(modifiedTree, compare, [1, 100]);
//or
const safeAdd = makeAdd(compare);
const modifiedTree = safeAdd(tree, 11);
const reModifiedTree = safeAdd(modifiedTree, [1, 100]);

// Schema of "tree"     =>     "modifiedTree"      =>   "reModifiedTree"
//                      |                          |
//       10             |            10            |            10
//    /     \           |         /     \          |         /     \
//   2      32          |        2      32         |        2      32
//    \    /  \         |         \    /  \        |      /  \    /  \
//     5  13  89        |          5  13  89       |     1    5  13  89
//            /         |            /   /         |            /   /  \
//          50          |           11  50         |           11  50   100

remove

Removes a (or list of) given node(s) from the given binary search tree with the given compare function and returns a new tree, without modifing the original tree in place.

:warning: Using another compare function than the one used to create the tree with toBST will of course f**k up the tree. A safer approach consists of using makeRemove. It curries a remove closure function with the given compare function.

const modifiedTree = remove(tree, compare, 10);
const reModifiedTree = remove(modifiedTree, compare, [13, 5]);
// or
const safeRemove = makeRemove(compare);
const modifiedTree = safeRemove(tree, 10);
const reModifiedTree = safeRemove(modifiedTree, [13, 5]);

// Schema of "tree"     =>     "modifiedTree"      =>   "reModifiedTree"
//                      |                          |
//       10             |            13            |             32
//    /     \           |         /     \          |          /     \
//   2      32          |        2      32         |         2      89
//    \    /  \         |         \       \        |                /
//     5  13  89        |          5      89       |              50
//            /         |                /         |
//          50          |              50          |

find, findFromPath

Finds a given node into the given binary search tree with the given compare function.

:warning: Using another compare function than the one used to create the tree with toBST will of course f**k up the search. A safer approach consists of using makeFind. It curries a find closure function with the given compare function.

// Schema of "tree"
//
//       10
//    /     \
//   2      32
//    \    /  \
//     5  13  89
//           /
//         50

const result = find(tree, compare, 13); // { node: { data: [13] }, path: ['right', 'left'] }
const resultFromPath = findFromPath(tree, compare, ['right', 'left']); // { node: { data: [13] }, path: ['right', 'left'] }
// or
const safeFind = makeFind(compare);
const result = safeFind(tree, 13); // { node: { data: [13] }, path: ['right', 'left'] }

const safeFindFromPath = makeFindFromPath(compare);
const resultFromPath = safeFindFromPath(tree, ['right', 'left']); // { node: { data: [13] }, path: ['right', 'left'] }

findLowestAncestor

Finds the lowest common ancestor of two given nodes into the given binary search tree with the given compare function.

:warning: Using another compare function than the one used to create the tree with toBST will of course f**k up the search. A safer approach consists of using makeFindLowestAncestor. It curries a findLowestAncestor closure function with the given compare function.

// Schema of "tree"
//
//       10
//    /     \
//   2      32
//    \    /  \
//     5  13  89
//           /
//         50

const result = findLowestAncestor(tree, compare, 13, 50); // { node: { data: [32], ... }, path: ['right'] }
// or
const safeFind = makeFindLowestAncestor(compare);
const result = safeFind(tree, 13, 50); // { node: { data: [32], ... }, path: ['right'] }

find(Gt/Gte/Lt/Lte)

Finds all gt/gte/lt/lte nodes into the given binary search tree with the given compare function.

:warning: Using another compare function than the one used to create the tree with toBST will of course f**k up the search. A safer approach consists of using makeFind(Gt/Gte/Lt/Lte). It curries a find(Gt/Gte/Lt/Lte) closure function with the given compare function.

• findGt
• findGte
• findLt
• findLte

// Schema of "tree"
//
//       10
//    /     \
//   2      32
//    \    /  \
//     5  13  89
//           /
//         50

const results = findGte(tree, compare, 4).flatMap(({ node, path: _path }) => node.data[0]);
// [10, 5, 32, 13, 89, 50]
// or
const safeFindGte = makeFindGte(compare);
const results = safeFindGte(tree, 4).flatMap(({ node, path: _path }) => node.data[0]);
// [10, 5, 32, 13, 89, 50]

find(Min/Max)(Height), count

Finds the min (findMin) or the max (findMax) node of the tree. Finds the height of the min (findMinHeight) or the max (findMaxHeight) branch of the tree. Counts (count) the nodes in the tree

// Schema of "tree"
//
//       10
//    /     \
//   2      32
//    \    /  \
//     5  13  89
//           /
//         50

const min = findMin(tree).data[0]; // 2
const max = findMax(tree).data[0]; // 89
const minHeight = findMinHeight(tree); // 1
const maxHeight = findMaxHeight(tree); // 3
const length = count(tree); // 7

getDistanceBetweenNodes

Gets the distance between two given elements into the given binary search tree with the given compare function.

:warning: Using another compare function than the one used to create the tree with toBST will of course f**k up the search. A safer approach consists of using makeGetDistanceBetweenNodes. It curries a getDistanceBetweenNodes closure function with the given compare function.

// Schema of "tree"
//
//       10
//    /     \
//   2      32
//    \    /  \
//     5  13  89
//           /
//         50

const result = getDistanceBetweenNodes(tree, compare, 13, 50); // 3
// or
const safeFind = makeGetDistanceBetweenNodes(compare);
const result = safeFind(tree, 13, 50); // 3

traverse

Traverses a tree, invoking the callback function on each visited node.

• (DFS) traverseInOrder
• (DFS) traverseInOrderReverse
• (DFS) traversePreOrder
• (DFS) traversePreOrderReverse
• (DFS) traversePostOrder
• (DFS) traversePostOrderReverse
• (BSF) traverseLevelOrder
• (BSF) traverseLevelOrderReverse

• DFS: Depth-First Search traversal
• BFS: Breadth-First Search traversal

// Schema of "tree"
//
//       10
//    /     \
//   2      32
//    \    /  \
//     5  13  89
//           /
//         50

const collect = (collection: number[]) => (node: { data: number[] }) => {
    node.data.forEach((e) => collection.push(e));
};

const elements = [];

traverseInOrder(collect(elements), tree);
// elements: [2, 5, 10, 13, 32, 50, 89]
traverseInOrderReverse(collect(elements), tree);
// elements: [89, 50, 32, 13, 10, 5, 2]
traversePreOrder(collect(elements), tree);
// elements: [10, 2, 5, 32, 13, 89, 50]
traversePreOrderReverse(collect(elements), tree);
// elements: [10, 32, 89, 50, 13, 2, 5]
traversePostOrder(collect(elements), tree);
// elements: [5, 2, 13, 50, 89, 32, 10]
traversePostOrderReverse(collect(elements), tree);
// elements: [50, 89, 13, 32, 5, 2, 10]
traverseLevelOrder(collect(elements), tree);
// elements: [10, 2, 32, 5, 13, 89, 50]
traverseLevelOrderReverse(collect(elements), tree);
// elements: [10, 32, 2, 89, 13, 5, 50]

toArray

Converts the given binary search tree to an array sorted as traversed:

• (DFS) toArrayInOrder
• (DFS) toArrayInOrderReverse
• (DFS) toArrayPreOrder
• (DFS) toArrayPreOrderReverse
• (DFS) toArrayPostOrder
• (DFS) toArrayPostOrderReverse
• (BFS) toArrayLevelOrder
• (BFS) toArrayLevelOrderReverse

• DFS: Depth-First Search traversal
• BFS: Breadth-First Search traversal

// Schema of "tree"
//
//       10
//    /     \
//   2      32
//    \    /  \
//     5  13  89
//           /
//         50

const a = toArrayInOrder(tree);
// [2, 5, 10, 13, 32, 50, 89]
const b = toArrayInOrderReverse(tree);
// [89, 50, 32, 13, 10, 5, 2]
const c = toArrayPreOrder(tree);
// [10, 2, 5, 32, 13, 89, 50]
const d = toArrayPreOrderReverse(tree);
// [10, 32, 89, 50, 13, 2, 5]
const e = toArrayPostOrder(tree);
// [5, 2, 13, 50, 89, 32, 10]
const f = toArrayPostOrderReverse(tree);
// [50, 89, 13, 32, 5, 2, 10]
const g = toArrayLevelOrder(tree);
// [10, 2, 32, 5, 13, 89, 50]
const h = toArrayLevelOrderReverse(tree);
// [10, 32, 2, 89, 13, 5, 50]

isLeaf, isBranch

Assesses if the given tree/node is a leaf (has no left nor right prop) (isLeaf) or a branch (has a left or a right prop or both) (isBranch).

// Schema of "tree"
//
//       10
//    /     \
//   2      32
//    \    /  \
//     5  13  89
//           /
//         50

const isLeafA = isLeaf(tree.left.left); // true
const isLeafB = isLeaf(tree); // false

const isBranchA = isBranch(tree); // true
const isBranchB = isBranch(tree.left.left); // false

hasLeft, hasRight

Assesses if the given tree/node has a left branch (has a left prop) (hasLeft) or a right branch (has a right prop) (hasRight).

// Schema of "tree"
//
//       10
//    /     \
//   2      32
//    \    /  \
//     5  13  89
//           /
//         50

const hasLeftA = hasLeft(tree); // true
const hasLeftB = hasLeft(tree.left); // false

const hasRightA = hasRight(tree); // true
const hasRightB = hasRight(tree.left.left); // false

makeCompareUtils

As the compare function is centric, for both the creation and the traversals of the BTS, a good practice is to create all the necessary utils, along with it. This will be DRY and ensure reusability and consistency.

// compare-alpha.ts
export const compareAlpha = (a: Hero, b: Hero) => a.name.localeCompare(b.name);
export const {
    toBST: toBSTAlpha,
    add: addAlpha,
    remove: removeAlpha,
    find: findAlpha,
    findLowestAncestor: findLowestAncestorAlpha,
    findGt: findGtAlpha,
    findGte: findGteAlpha,
    findLt: findLtAlpha,
    findLte: findLteAlpha,
    balance: balanceAlpha,
    getDistanceBetweenNodes: getDistanceBetweenNodesAlpha,
} = makeCompareUtils(compareAlpha);

// other-file.ts
import {
    compareAlpha,
    toBSTAlpha,
    addAlpha,
    removeAlpha,
    findAlpha,
    findLowestAncestorAlpha,
    findGtAlpha,
    findGteAlpha,
    findLtAlpha,
    findLteAlpha,
    balanceAlpha,
    getDistanceBetweenNodesAlpha,
} from './compare-alpha';

const tree = toBSTAlpha([{ name: 'Anakin' }]);

const updatedTree = pipe(
    (t) => addAlpha(t, { name: 'Yoda' }),
    (t) => removeAlpha(t, { name: 'Luke' }),
    (t) => balanceAlpha(t),
    (t) => findGtAlpha({ name: 'Yoda' })
)(tree);

The infamous BinarySearchTree class

While diverging from the functional approach, the BinarySearchTree class offers many advantages, depending on the situation:

Pros:

• Natural chaining
• Tree state encapsulation
• Compare function encapsulation
• Has all methods listed as functions before

Cons:

• No tree shaking of unused methods, obviously

Let's rewrite the Star Wars example with this approach:

type Hero = { name: string };

const compareAlpha = (a: Hero, b: Hero) => a.name.localeCompare(b.name);

const heroes: Hero[] = [
    { name: 'Han' },
    { name: 'Anakin' },
    { name: 'Leia' },
    { name: 'Luke' },
    { name: 'Padme' },
    { name: 'Lando' },
    { name: 'Chewie' },
];

const bst = new BinarySearchTree(heroes, compareAlpha, { isBalanced: false });
// Schema of bst.tree
//
//             Han
//           /     \
//     Anakin       Leia
//           \     /    \
//       Chewie  Lando   Luke
//                         \
//                        Padme

bst.add({ name: 'Yoda' })
    .add({ name: 'Obiwan' })
    .add([{ name: 'Boba' }, { name: 'Grogu' }])
    .remove([{ name: 'Han' }, { name: 'Padme' }])
    .remove({ name: 'Luke' });

// Schema of bst.tree, after update
//
//            Lando
//           /     \
//     Anakin       Leia
//         \            \
//       Chewie        Obiwan
//        /    \            \
//      Boba  Grogu        Yoda

bst.findMin().data[0].name; // Anakin
bst.findMax().data[0].name; // Yoda
bst.find({ name: 'Grogu' }).node.data[0].name; // Grogu
bst.find({ name: 'Grogu' }).path; // ['left', 'right', 'right']
// Thanks to the compare function, the search will traverse like this:
// Lando -> Anakin -> Chewie -> Grogu