Lesson 3

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.

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:

`1 50 2 / \ 3 30 70 4 / \ / \ 520 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.

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.

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`1const { BinarySearchTree } = require('@datastructures-js/binary-search-tree'); 2 3// Initialize a binary search tree with a custom comparison function for strings 4const bst = new BinarySearchTree(); 5 6// Inserting single elements (strings) 7const items = ['banana', 'apple', 'pear', 'orange']; 8items.forEach(item => bst.insert(item)); 9 10// Using the BST methods to find lower and upper bounds 11const lowerBound = bst.lowerBound('apricote'); 12console.log('Lower bound for apricote:', lowerBound ? lowerBound._value : 'Not found'); 13// Output: Lower bound for apple: apple 14 15const upperBound = bst.upperBound('apricote'); 16console.log('Upper bound for apricote:', upperBound ? upperBound._value : 'Not found'); 17// Output: Upper bound for apple: banana 18 19// Remove 'apple' and print the removed item 20const item = bst.find('apple'); 21bst.remove('apple'); 22console.log('Deleted item:', item ? item._value : 'Not found'); 23// Output: Deleted item: apple 24 25// Attempt to fetch a nonexistent key 26const value = bst.find('apple'); 27console.log('Value:', value ? value._value : 'Not found'); 28// Output: Value: Not found 29 30// Peek at the minimum and maximum items 31const minItem = bst.min(); 32console.log('Min item:', minItem ? minItem._value : 'Tree is empty'); 33// Output: Min item: banana 34 35const maxItem = bst.max(); 36console.log('Max item:', maxItem ? maxItem._value : 'Tree is empty'); 37// Output: Max item: pear`

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:

JavaScript`1const { BinarySearchTree } = require('@datastructures-js/binary-search-tree'); 2 3const entries = [['banana', 3], ['apple', 4], ['pear', 1], ['orange', 2]]; 4const compareArrays = (a, b) => a[0].localeCompare(b[0]); 5const bst = new BinarySearchTree(compareArrays); 6entries.forEach(entry => bst.insert(entry)); 7 8const value = bst.find(['apple']); 9console.log('Value:', value ? value._value[1] : 'Not found'); 10// Output: 4 11 12const lowerBound = bst.lowerBound(['apple'], false); 13console.log('Exclusive lower bound for apple:', lowerBound ? lowerBound._value : 'Not found'); 14// Output: Exclusive lower bound for apple: Not found 15 16const upperBound = bst.upperBound(['apple'], false); 17console.log('Exclusive upper bound for apple:', upperBound ? upperBound._value : 'Not found'); 18// Output: Exclusive upper bound for apple: [ 'banana', 3 ] 19 20const minItem = bst.min(); 21console.log('Min item:', minItem ? minItem._value : 'Tree is empty'); 22// Output: Min item: [ 'apple', 4 ] 23 24const maxItem = bst.max(); 25console.log('Max item:', maxItem ? maxItem._value : 'Tree is empty'); 26// Output: Max item: [ 'pear', 1 ]`

Here, 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.

Congratulations! You have successfully delved into `Binary Search Trees`

in JavaScript. This exploration included understanding how to utilize the `@datastructures-js/binary-search-tree`

library to manage sorted data functionality in JavaScript, creating instances with single elements and key-value pairs, and navigating the valuable methods associated with this data structure. Keep practicing to fortify your understanding and expand your skill set!