Binary search tree using JavaScript ES6-Typescript

A Binary Search Tree (BST) is a data structure composed of nodes. Each node has a key that determines the node’s position in the tree. (The node may also have a “value” field where additional data is stored.) Specifically, each node has a left child, a right child, and a parent (some of which may be null). In this post, I will show you how to create a binary search tree in JavaScript ES6/TypeScript.

Table of Contents

1. Create Binary Search Tree
2. Inorder Traversal
3. Preorder Traversal
4. Find Max in BST
5. Find Min in BST
6. Level Order Traversal

Create Binary Search Tree

To start with, let’s define the basic structure of our Binary Search Tree. We will have two classes: TreeNode and BinarySearchTree.

Binary Search Tree Using JavaScript ES6/TypeScript

class TreeNode {
  constructor(
    public data: number,
    public left: TreeNode = null,
    public right: TreeNode = null
  ) {}
}

export class BinarySearchTree {
  constructor(private root: TreeNode = null) {}

  public insert(data: number): void {
    let newNode = new TreeNode(data);
    if (!this.root) {
      this.root = newNode;
      return;
    }

    let current = this.root;
    while (true) {
      if (data < current.data) {
        if (current.left === null) {
          current.left = newNode;
          return;
        }
        current = current.left;
      } else if (data > current.data) {
        if (current.right === null) {
          current.right = newNode;
          return;
        }
        current = current.right;
      }
    }
  }

  // Other methods will be implemented here
}

The TreeNode class represents a node in the BST, and the BinarySearchTree class is the tree itself, which manages all operations like insertion, traversal, and searching.

Inorder Traversal

Inorder traversal of a BST gives nodes in a non-decreasing order. Let’s implement an inorderTraversal method:

public inorderTraversal(node: TreeNode = this.root): void {
  if (node !== null) {
    this.inorderTraversal(node.left);
    console.log(node.data);
    this.inorderTraversal(node.right);
  }
}

Preorder Traversal

Preorder traversal visits the root node first, followed by the left subtree, and then the right subtree:

public preorderTraversal(node: TreeNode = this.root): void {
  if (node !== null) {
    console.log(node.data);
    this.preorderTraversal(node.left);
    this.preorderTraversal(node.right);
  }
}

Find Max in BST

To find the maximum value in a BST, we traverse the right subtree until we reach the rightmost node:

public findMax(): number {
  if (!this.root) return null;
  let current = this.root;
  while (current.right !== null) {
    current = current.right;
  }
  return current.data;
}

Find Min in BST

To find the minimum value in a BST, we traverse the left subtree until we reach the leftmost node:

public findMin(): number {
  if (!this.root) return null;
  let current = this.root;
  while (current.left !== null) {
    current = current.left;
  }
  return current.data;
}

Level Order Traversal

Level Order Traversal visits nodes level by level from left to right. We use a queue to help implement this traversal:

public levelOrderTraversal(): void {
  if (!this.root) return;
  let queue: TreeNode[] = [];
  queue.push(this.root);

  while (queue.length > 0) {
    let current = queue.shift();
    console.log(current.data);

    if (current.left !== null) queue.push(current.left);
    if (current.right !== null) queue.push(current.right);
  }
}

Conclusion

By implementing these methods, we’ve covered the basic operations of a Binary Search Tree, such as insertion, different types of tree traversals, and finding the minimum and maximum values. These operations are fundamental in many applications, including database indexing, expression parsing, and more.