Binary Search Trees in JavaScript

Binary Search Trees (BST) in JavaScript

Hello again! This lesson's topic is Binary Search Trees (BST) in JavaScript. A BST is a data structure that stores key-value pairs in an ordered manner, making data manipulation organized and efficient. JavaScript 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 JavaScript.

What is a Binary Search Tree

A Binary Search Tree (BST) is a node-based data structure where each node has at most two children referred to as the left child and the right child. The key in each node must be greater than (or equal to) any key stored in the left subtree, and less than (or equal to) any key stored in the right subtree. This property makes the binary search tree an efficient data structure for operations such as insertion, deletion, and searching. Example of a Binary Search Tree Consider the following BST: 50 / \ 30 70 / \ / \ 20 40 60 80 In this tree: The root node is 50. The left subtree of 50 contains nodes 30, 20, and 40. The right subtree of 50 contains nodes 70, 60, and 80. The key in the root node (50) is greater than all keys in its left subtree (20, 30, 40) and less than all keys in its right subtree (60, 70, 80). And this property is satisfied for all nodes, not just the root. This property allows for efficient searching, as you can disregard half of the remaining tree at each step, leading to an average time complexity of O(log n) for search operations. Now, let's move forward and see how to implement and work with BSTs in JavaScript using the @datastructures-js/binary-search-tree library.

Traversing BST Methods

Using the BinarySearchTree, we can implement several useful methods for managing and traversing the BST: lowerBound(searchKey) : This method finds the node with the biggest key less or equal a given searchKey . upperBound(searchKey) : This method finds the node with the smallest key bigger or equal a given searchKey . remove(searchKey) : Removes the specified key and its associated value. find(searchKey) : Returns the node for the key if it exists. min() : Returns the node with the smallest key. max() : Returns the node with the largest key.

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 library to handle sorted elements. Here's how to get started:

JavaScript

const { BinarySearchTree } = require('@datastructures-js/binary-search-tree');

// Initialize a binary search tree with a custom comparison function for strings
const bst = new BinarySearchTree();

// Inserting single elements (strings)
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

const { BinarySearchTree } = require('@datastructures-js/binary-search-tree');

// Initialize a binary search tree with a custom comparison function for strings
const bst = new BinarySearchTree();

// Inserting single elements (strings)
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 JavaScript code, which incorporates key-value pairs represented as arrays. To manage these pairs, we will initialize the BinarySearchTree with a custom comparison function: