Binary Search Trees in TypeScript

Binary Search Trees (BST) in TypeScript

Hello again! This lesson's topic is Binary Search Trees (BST) in TypeScript. A BST is a data structure that stores key-value pairs in an ordered manner, making data manipulation organized and efficient. TypeScript doesn't include a built-in binary search tree data structure. However, we can utilize the @datastructures-js/binary-search-tree library to manage our data in a sorted and efficient manner. Today's goal is to work with BSTs using TypeScript.

What is a Binary Search Tree

O(log n)

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

     50
   /    \
 30     70
 / \    / \
20 40  60 80

TypeScript

import { BinarySearchTree } from '@datastructures-js/binary-search-tree';

// Initialize a binary search tree
const bst = new BinarySearchTree<string>();

// Inserting elements
const items = ['banana', 'apple', 'pear', 'orange'];
items.forEach(item => bst.insert(item));

// Using the BST methods to find lower and upper bounds
const lowerBound = bst.lowerBound('apricot');
console.log('Lower bound for apricot:', lowerBound ? lowerBound.getValue() : 'Not found');
// Output: Lower bound for apricot: apple

const upperBound = bst.upperBound('apricot');
console.log('Upper bound for apricot:', upperBound ? upperBound.getValue() : 'Not found');
// Output: Upper bound for apricot: banana

// Remove 'apple' and print the removed item
const item = bst.find('apple');
bst.remove('apple');
console.log('Deleted item:', item ? item.getValue() : 'Not found');
// Output: Deleted item: apple

// Attempt to fetch a nonexistent key
const value = bst.find('apple');
console.log('Value:', value ? value.getValue() : 'Not found');
// Output: Value: Not found

// Peek at the minimum and maximum items
const minItem = bst.min();
console.log('Min item:', minItem ? minItem.getValue() : 'Tree is empty');
// Output: Min item: banana

const maxItem = bst.max();
console.log('Max item:', maxItem ? maxItem.getValue() : 'Tree is empty');
// Output: Max item: pear

import { BinarySearchTree } from '@datastructures-js/binary-search-tree';

// Initialize a binary search tree
const bst = new BinarySearchTree<string>();

// Inserting elements
const items = ['banana', 'apple', 'pear', 'orange'];
items.forEach(item => bst.insert(item));

// Using the BST methods to find lower and upper bounds
const lowerBound = bst.lowerBound('apricot');
console.log('Lower bound for apricot:', lowerBound ? lowerBound.getValue() : 'Not found');
// Output: Lower bound for apricot: apple

const upperBound = bst.upperBound('apricot');
console.log('Upper bound for apricot:', upperBound ? upperBound.getValue() : 'Not found');
// Output: Upper bound for apricot: banana

// Remove 'apple' and print the removed item
const item = bst.find('apple');
bst.remove('apple');
console.log('Deleted item:', item ? item.getValue() : 'Not found');
// Output: Deleted item: apple

// Attempt to fetch a nonexistent key
const value = bst.find('apple');
console.log('Value:', value ? value.getValue() : 'Not found');
// Output: Value: Not found

// Peek at the minimum and maximum items
const minItem = bst.min();
console.log('Min item:', minItem ? minItem.getValue() : 'Tree is empty');
// Output: Min item: banana

const maxItem = bst.max();
console.log('Max item:', maxItem ? maxItem.getValue() : 'Tree is empty');
// Output: Max item: pear

TypeScript

import { BinarySearchTree } from '@datastructures-js/binary-search-tree';

const entries: [string, number][] = [['banana', 3], ['apple', 4], ['pear', 1], ['orange', 2]];
const compareArrays = (a: [string, number], b: [string, number]) => a[0].localeCompare(b[0]);
const bst = new BinarySearchTree(compareArrays);
entries.forEach(entry => bst.insert(entry));

const valueNode = bst.find(['apple', 0]);
console.log('Value:', valueNode ? valueNode.getValue()[1] : 'Not found');
// Output: Value: 4

const lowerBound = bst.lowerBound(['apple', 0], false);
console.log('Exclusive lower bound for apple:', lowerBound ? lowerBound.getValue() : 'Not found');
// Output: Exclusive lower bound for apple: Not found

const upperBound = bst.upperBound(['apple', 0], false);
console.log('Exclusive upper bound for apple:', upperBound ? upperBound.getValue() : 'Not found');
// Output: Exclusive upper bound for apple: [ 'banana', 3 ]

const minItem = bst.min();
console.log('Min item:', minItem ? minItem.getValue() : 'Tree is empty');
// Output: Min item: [ 'apple', 4 ]

const maxItem = bst.max();
console.log('Max item:', maxItem ? maxItem.getValue() : 'Tree is empty');
// Output: Max item: [ 'pear', 1 ]

import { BinarySearchTree } from '@datastructures-js/binary-search-tree';

const entries: [string, number][] = [['banana', 3], ['apple', 4], ['pear', 1], ['orange', 2]];
const compareArrays = (a: [string, number], b: [string, number]) => a[0].localeCompare(b[0]);
const bst = new BinarySearchTree(compareArrays);
entries.forEach(entry => bst.insert(entry));

const valueNode = bst.find(['apple', 0]);
console.log('Value:', valueNode ? valueNode.getValue()[1] : 'Not found');
// Output: Value: 4

const lowerBound = bst.lowerBound(['apple', 0], false);
console.log('Exclusive lower bound for apple:', lowerBound ? lowerBound.getValue() : 'Not found');
// Output: Exclusive lower bound for apple: Not found

const upperBound = bst.upperBound(['apple', 0], false);
console.log('Exclusive upper bound for apple:', upperBound ? upperBound.getValue() : 'Not found');
// Output: Exclusive upper bound for apple: [ 'banana', 3 ]

const minItem = bst.min();
console.log('Min item:', minItem ? minItem.getValue() : 'Tree is empty');
// Output: Min item: [ 'apple', 4 ]

const maxItem = bst.max();
console.log('Max item:', maxItem ? maxItem.getValue() : 'Tree is empty');
// Output: Max item: [ 'pear', 1 ]

TypeScript

import { BinarySearchTree } from '@datastructures-js/binary-search-tree';

// Initialize a binary search tree
const bst = new BinarySearchTree<string>();

// Inserting elements
const items = ['banana', 'apple', 'pear', 'orange'];
items.forEach(item => bst.insert(item));

// Using the BST methods to find lower and upper bounds
const lowerBound = bst.lowerBound('apricot');
console.log('Lower bound for apricot:', lowerBound ? lowerBound.getValue() : 'Not found');
// Output: Lower bound for apricot: apple

const upperBound = bst.upperBound('apricot');
console.log('Upper bound for apricot:', upperBound ? upperBound.getValue() : 'Not found');
// Output: Upper bound for apricot: banana

// Remove 'apple' and print the removed item
const item = bst.find('apple');
bst.remove('apple');
console.log('Deleted item:', item ? item.getValue() : 'Not found');
// Output: Deleted item: apple

// Attempt to fetch a nonexistent key
const value = bst.find('apple');
console.log('Value:', value ? value.getValue() : 'Not found');
// Output: Value: Not found

// Peek at the minimum and maximum items
const minItem = bst.min();
console.log('Min item:', minItem ? minItem.getValue() : 'Tree is empty');
// Output: Min item: banana

const maxItem = bst.max();
console.log('Max item:', maxItem ? maxItem.getValue() : 'Tree is empty');
// Output: Max item: pear

TypeScript

import { BinarySearchTree } from '@datastructures-js/binary-search-tree';

const entries: [string, number][] = [['banana', 3], ['apple', 4], ['pear', 1], ['orange', 2]];
const compareArrays = (a: [string, number], b: [string, number]) => a[0].localeCompare(b[0]);
const bst = new BinarySearchTree(compareArrays);
entries.forEach(entry => bst.insert(entry));

const valueNode = bst.find(['apple', 0]);
console.log('Value:', valueNode ? valueNode.getValue()[1] : 'Not found');
// Output: Value: 4

const lowerBound = bst.lowerBound(['apple', 0], false);
console.log('Exclusive lower bound for apple:', lowerBound ? lowerBound.getValue() : 'Not found');
// Output: Exclusive lower bound for apple: Not found

const upperBound = bst.upperBound(['apple', 0], false);
console.log('Exclusive upper bound for apple:', upperBound ? upperBound.getValue() : 'Not found');
// Output: Exclusive upper bound for apple: [ 'banana', 3 ]

const minItem = bst.min();
console.log('Min item:', minItem ? minItem.getValue() : 'Tree is empty');
// Output: Min item: [ 'apple', 4 ]

const maxItem = bst.max();
console.log('Max item:', maxItem ? maxItem.getValue() : 'Tree is empty');
// Output: Max item: [ 'pear', 1 ]