<_

Data Structures: Binary Tree in TypeScript

Unraveling the Mysteries of Binary Trees in TypeScript

Introduction

Today, we're diving into the fascinating world of binary trees, specifically in the realm of TypeScript. Whether you're a seasoned programmer or just dipping your toes into the coding waters, understanding binary trees is like having a Swiss Army knife in your coding toolkit. So, buckle up and let's embark on this enlightening journey together!

What's a Binary Tree Anyway?

Before we jump into the nitty-gritty, let's clear the air about what a binary tree actually is. Picture a tree (yes, like the one outside your window), but flip it upside down. In this tree, each branch (or node, in geek speak) has at most two little offshoots (children). This structure is super handy for organizing data in a way that makes searching, inserting, and deleting operations efficient. It's like having a well-organized closet where you can find your favorite socks in a jiffy!

Key Characteristics:

  • Root of the Matter: Every tree has a root node, the big kahuna from which all other nodes stem.
  • Left and Right: Each node can have up to two children, conveniently named left and right.
  • Leaf It Out: Nodes without children are called leaves. They're the endpoints of the tree.

Implementing a Binary Tree in TypeScript

Alright, let's roll up our sleeves and get coding! TypeScript, with its static typing, is like having a GPS for our coding journey, guiding us and reducing the chances of getting lost (or, you know, making errors).

Defining the Node:

First things first, let's define what a node looks like.

class TreeNode<T> {
    value: T;
    left: TreeNode<T> | null;
    right: TreeNode<T> | null;

    constructor(value: T) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

Here, we've created a generic TreeNode class. It's like saying, "Hey, our tree can store any type of data, not just numbers or strings!"

Creating the Binary Tree Class:

Now, let's build the actual tree.


class BinaryTree<T> {
    root: TreeNode<T> | null;

    constructor() {
        this.root = null;
    }

    // Methods will go here
}

Our BinaryTree class is starting to take shape, with a root to anchor it.

Adding the Bells and Whistles A tree isn't much use without some functionality. Let's add some methods to our BinaryTree class.

Inserting Nodes:

Inserting nodes is like finding the perfect spot for your coffee mug on a cluttered desk.


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

insert(value: T): void {
    const newNode = new Node(value)

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

private insertNode(node: TreeNode<T>, newNode: TreeNode<T>): void {
   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)
		}
	}
}

Searching for Nodes:

Looking for a node is like playing hide and seek with your data.


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)
		}
	}
}

Traversing the Tree:

Traversing is like taking a leisurely stroll through your tree, visiting each node.

In-Order Traversal:


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

Pre-Order Traversal:


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

Post-Order Traversal:


postOrderTraversal(root: Node | null) {
	// Depth First Search
	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() {
	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)
		}
	}
}

Min Value:

It may be useful to find the minimum value in your tree.


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

Max Value:

Since we are looking for minimums, we may also want to find the maximums.


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

Deleting Nodes

I think deleting a node may actually also be pretty nifty!


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
}

Putting it all together


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

export default class BinarySearchTree {
	constructor() {
		this.root = null
	}
	root: Node | null

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

	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)
			}
		}
	}

	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)
			}
		}
	}

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

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

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

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

	levelOrderTraversal() {
		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)
			}
		}
	}

	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)
		}
	}

	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
	}
}

Practical Tips and Tricks

  • TypeScript's Generics are Your Friend: They make your tree flexible and reusable.
  • Test, Test, and Test Again: Always test your tree with different data types and scenarios.
  • Keep It Clean: Refactor and comment your code. Future you will be grateful.

Conclusion

And there you have it! You've just built a binary tree in TypeScript, and that's no small feat. Remember, like any journey, mastering binary trees takes practice and patience. Keep experimenting, keep coding, and most importantly, keep having fun!

Happy coding, and may your binary trees always be balanced!