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

Using Binary Search Trees

We will use the BinarySearchTree class from the @datastructures-js/binary-search-tree package to handle sorted elements. Here's how to get started:

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

Storing Key-Value Pairs

Consider the following TypeScript code, which demonstrates storing key-value pairs using arrays. To manage these pairs, we will initialize the BinarySearchTree with a custom comparison function:

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 ]

In this example, we pass a custom comparison function compareArrays to the BinarySearchTree constructor. This function takes two arguments, a and b, which are arrays representing key-value pairs. The function compares the first elements of these arrays (the keys) using localeCompare to ensure the tree is sorted based on the keys in lexicographical order.

In the lowerBound and upperBound methods, the second parameter is a boolean that dictates whether the search is inclusive or exclusive:

By default, if the second parameter is not provided or set to true, the search is inclusive, meaning it will return the node with the search key if it exists.
If the second parameter is false, the search is exclusive, meaning it will find the next closest node and exclude the node with the exact search key. This is useful for scenarios where you need to find the bounds around a given key.

Binary Search Trees (BST) in TypeScript

What is a Binary Search Tree

Join the 1M+ learners on CodeSignal

Traversing BST Methods

Using Binary Search Trees

Storing Key-Value Pairs

Lesson Summary