Binary Search Trees 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.

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.

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.