<_

Data Structures: Binary Search Tree in TypeScript

Mastering Binary Search Trees in TypeScript: A Programmer's Guide

Introduction

Hey there, fellow coders! Today, we're diving into the fascinating world of Binary Search Trees (BSTs) and how they come to life in TypeScript. Whether you're a seasoned pro or just starting, understanding BSTs is like having a Swiss Army knife in your programming toolkit. So, let's embark on this journey together and unravel the mysteries of BSTs in TypeScript.

What is a Binary Search Tree?

Definition

A Binary Search Tree is a node-based data structure where each node has at most two children. Here's the kicker: it's designed in such a way that the left child is always less than the parent node, and the right child is always greater. This unique property makes BSTs a go-to for efficient searching, insertion, and deletion operations.

Why Use a BST?

  • Speedy Searches: Thanks to its structure, finding elements is a breeze.
  • Dynamic Data Handling: It can easily grow or shrink, adapting to your data needs.
  • Sorted Data: It keeps your data neatly sorted, making operations like finding the min or max value a walk in the park.


Starting with the Queue:

In the following article on a queue in typescript, we covered the queue. So for brevity, I will show the code here. But i'd encourage a read through if you are not familiar with it. Since we will be using the queue in our binary search tree, here it is:


export class Queue {
	items: any[keyof string | number] | any
	rear: number
	front: number

	constructor() {
		this.items = {}
		this.rear = 0
		this.front = 0
	}

	enqueue(element: any) {
		this.items[this.rear] = element
		this.rear++
	}

	dequeue() {
		const item = this.items[this.front]
		delete this.items[this.front]
		this.front++
		return item
	}

	isEmpty() {
		return this.front - this.rear === 0
	}

	peek() {
		return this.items[this.front]
	}

	size() {
		return this.rear - this.front
	}

	print() {
		console.log(this.items)
	}

	clear() {
		this.items = {}
		this.rear = 0
		this.front = 0
	}
}


Implementing a BST in TypeScript

The Node Class

Secondly, here is our Node. Will be using the node to track the node value, and the pointer to the connected nodes. The left node in the tree is always lower than the value of your node. And the right node is always higher.


class Node {
	constructor(value: any) {
		this.value = value
		this.left = null
		this.right = null
	}
	value: any
	left: any
	right: any
}

The BinarySearchTree Class

Now, let's create the BST class itself. In any file you want, in my case, I added it to it's own file called binarySearchTree.ts, I will export default the class. That way I can reuse this class in various areas of my projects.


export default class BinarySearchTree<T> {
    root: Node<T> | null;

    constructor() {
        this.root = null;
    }

    // Methods will be added here
}

Core Operations

We will need a bunch of methods to make this class useful. To start, it may be handy to know if it is empty or not. We will do this with the isEmpty() method:


    isEmpty() {
		return this.root === null
	}

Which is pretty self explanatory. It checks to see if the root has a node value. If not, then there is no node.


Insertion

Up next, we need the ability to add a node. We will do this by inserting a new value into our BST. Which is like a mini-maze. But we will do this with two methods. Insert, and insertNode (which will be private).


insert(value: any) {
	const newNode = new Node(value)

	if (this.isEmpty()) {
		this.root = newNode
		return this
	} else {
		this.insertNode(this.root!, newNode)
	}
}

private insertNode(root: Node, newNode: Node) {
	if (newNode.value < root.value) {
		if (root.left === null) {
			root.left = newNode
			return
		} else {
			this.insertNode(root.left, newNode)
		}
	} else {
		if (root.right === null) {
			root.right = newNode
			return
		} else {
			this.insertNode(root.right, newNode)
		}
	}
}

First we create the private insertNode method which takes the root node, and the new Node as values. It will compare the left and right nodes on the root. If it's null then that is the last node and we insert there. If the new value is less than the current value, it goes to the left, if larger it goes to the right. And it does this comparison all along the tree branches until we hit the null value, and insert.

So when we use this, we will use or insert method, which takes only the value. This will check if it's empty with our isEmpty() method. If it is, it applies the node right there. If not, it will  use our insertNode() method we just created. And that will run recursively until the value is inserted. Pretty simple. Almost like magic.

Searching

Looking for a value? Let's see how we can find it.


search(root: Node | null, value: any): boolean {
	if (!root) {
		return false
	} else {
		if (root.value === value) {
			return true
		} else if (value < root.value) {
			return this.search(root.left, value)
		} else {
			return this.search(root.right, value)
		}
	}
}


This is pretty simple. It will recursively compare the value you are searching for, checking if it equals the value of the current node, or if it is greater than or equal to the left or right nodes and moves along the branches until null or the value is found!


Deletion

Removing a value involves a bit of a dance, ensuring the BST remains valid. We will do a similar method to the insertion requiring two methods, one private and one public.


delete(value: number) {
	this.deleteNode(this.root, value)
}



private deleteNode(root: Node | null, value: number) {
	if (root === null) {
		return root
	}

	if (value < root.value) {
		root.left = this.deleteNode(root.left, value)
	} else if (value > root.value) {
		root.right = this.deleteNode(root.right, value)
	} else {
		if (!root.left && !root.right) {
			return null
		}

		if (!root.left) {
			return root.right
		} else if (!root.right) {
			return root.left
		}

		root!.value = this.minValue(root!.right)
		root!.right = this.deleteNode(root!.right, root!.value)
	}
	return root
}

Advanced Concepts

Traversals

Exploring a BST can be done in various ways, each with its unique flavor.

In-Order Traversal


inOrderTraversal(root: Node | null) {
	if (root) {
		this.inOrderTraversal(root.left)
		console.log(root.value)
		this.inOrderTraversal(root.right)
	}
}

Pre-Order Traversal


preOrderTraversal(root: Node | null) {
	/**
	 * @DepthFirstSearch - PreOrder Traversal
	 */
	if (root) {
		console.log(root.value)
		this.preOrderTraversal(root.left)
		this.preOrderTraversal(root.right)
	}
}

Post-Order Traversal


postOrderTraversal(root: Node | null) {
	if (root) {
		this.postOrderTraversal(root.left)
		this.postOrderTraversal(root.right)
		console.log(root.value)
	}
}

Reverse Order Traversal


reverseOrderTraversal(root: Node | null) {
	if (root) {
		this.postOrderTraversal(root.right)
		console.log(root.value)
		this.postOrderTraversal(root.left)
	}
}

Level Order Traversal


levelOrderTraversal() {
	// Breadth First Search
	const queue = new Queue()
	queue.enqueue(this.root)
	while (!queue.isEmpty()) {
		const node = queue.dequeue()
		console.log(node.value)
		if (node.left) {
			queue.enqueue(node.left)
		}
		if (node.right) {
			queue.enqueue(node.right)
		}
	}
}


Searching for High's and Low's

Here are another couple useful methods for searching for the highest and lowest values: We will call them minValue() and maxValue():


    minValue(root: Node | null): number | null {
		if (root === null) {
			return null
		} else if (!root.left) {
			return root.value
		} else {
			return this.minValue(root.left)
		}
	}

	maxValue(root: Node | null): number | null {
		if (root === null) {
			return null
		} else if (!root.right) {
			return root.value
		} else {
			return this.maxValue(root.right)
		}
	}


Practical Applications

Real-World Use Cases

  • Database Indexing: BSTs are the backbone of efficient database indexing.
  • Autocomplete Features: Ever wondered how your search bar predicts text? Yep, BSTs at play!
  • Gaming: From AI decision-making to game state management, BSTs are game-changers.

Tips for Optimization

  • Balancing Act: Keep your BST balanced for optimal performance.
  • TypeScript's Generics: Leverage TypeScript's generics for flexible and reusable BSTs.
  • Memory Management: Be mindful of memory usage, especially with large datasets.

Conclusion

Binary Search Trees are a powerhouse in the world of data structures, and TypeScript brings them to life with elegance and efficiency. Whether you're building a complex application or simply love algorithms, mastering BSTs in TypeScript is a skill that'll pay dividends. So, keep practicing, keep coding, and let the power of BSTs elevate your programming prowess to new heights!