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.

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:

Copy to clipboard
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.

Due to its sorted nature, a BST enables binary search on the data, leading to the following time complexities for operations:

• Search: $O(log n)$ on average, as each comparison allows us to ignore half of the remaining tree. This efficiency depends on the tree's balance; if the tree becomes unbalanced (e.g., resembling a linked list), the time complexity could degrade to $O(n)$.
• Insertion: $O(log n)$ on average, since each step through the tree involves comparing values and deciding to move left or right. In a balanced BST, this makes insertions efficient.
• Deletion: $O(log n)$ on average. Deletion is more complex than insertion because it depends on the node’s location and the number of children it has. For example:
  • If the node has no children, we can remove it directly.
  • If it has one child, we bypass the node by linking its parent directly to the child.
  • If it has two children, we need to replace it with its in-order successor (the smallest node in the right subtree) or in-order predecessor (the largest node in the left subtree).

Now, let's move forward and see how to implement and work with BSTs in TypeScript 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: T): This method finds the node with the biggest key less than or equal to a given searchKey.
• upperBound(searchKey: T): This method finds the node with the smallest key greater than or equal to a given searchKey.
• remove(searchKey: T): Removes the specified key and its associated value.
• find(searchKey: T): 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 package to handle sorted elements. Here's how to get started:

TypeScript
Copy to clipboard
1import { BinarySearchTree } from '@datastructures-js/binary-search-tree';
2
3// Initialize a binary search tree
4const bst = new BinarySearchTree<string>();
5
6// Inserting elements
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('apricot');
12console.log('Lower bound for apricot:', lowerBound ? lowerBound.getValue() : 'Not found');
13// Output: Lower bound for apricot: apple
14
15const upperBound = bst.upperBound('apricot');
16console.log('Upper bound for apricot:', upperBound ? upperBound.getValue() : 'Not found');
17// Output: Upper bound for apricot: banana
18
19// Remove 'apple' and print the removed item
20const item = bst.find('apple');
21bst.remove('apple');
22console.log('Deleted item:', item ? item.getValue() : '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.getValue() : '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.getValue() : 'Tree is empty');
33// Output: Min item: banana
34
35const maxItem = bst.max();
36console.log('Max item:', maxItem ? maxItem.getValue() : 'Tree is empty');
37// Output: Max item: pear

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

Congratulations! You have successfully delved into Binary Search Trees in TypeScript. This exploration included understanding how to utilize the @datastructures-js/binary-search-tree library to manage sorted data functionality, 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!