Implement a binary search tree (BST)

Binary Search Trees (BSTs) are fundamental data structures in computer science. They offer efficient searching, insertion, and deletion operations, making them useful for various applications. This post will guide you through implementing a BST in JavaScript, complete with code examples.

A BST is a tree-like structure where each node has at most two children, referred to as the left and right child. The key property of a BST is that for every node, all nodes in its left subtree have keys less than the node’s key, and all nodes in its right subtree have keys greater than the node’s key. This ordering allows for efficient searching.

Let’s start with the Node class:

class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

This simple class represents a single node in our BST, storing its data and references to its left and right children.

Next, let’s create the BST class itself:

class BST {
  constructor() {
    this.root = null;
  }

  insert(data) {
    let newNode = new Node(data);
    if (this.root === null) {
      this.root = newNode;
      return;
    }

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


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

  //Inorder traversal (prints data in ascending order)
  inorder(node) {
    if (node !== null) {
      this.inorder(node.left);
      console.log(node.data);
      this.inorder(node.right);
    }
  }
}

The insert method adds a new node to the BST, maintaining the BST property. The search method efficiently searches for a specific data value. The inorder method demonstrates a tree traversal technique; inorder traversal visits nodes in ascending order of their keys.

Here’s how to use the BST:

let bst = new BST();
bst.insert(8);
bst.insert(3);
bst.insert(10);
bst.insert(1);
bst.insert(6);
bst.insert(14);

console.log("Search for 6:", bst.search(6)); // Output: true
console.log("Search for 7:", bst.search(7)); // Output: false

console.log("Inorder traversal:");
bst.inorder(bst.root); // Output: 1 3 6 8 10 14

This example demonstrates the basic insertion and search functionalities. Remember that for larger datasets, more complex implementations might be necessary to handle edge cases and optimize performance. Deletion from a BST is a more complex operation and is beyond the scope of this basic example. Implementing deletion would involve handling cases where a node has zero, one, or two children. Consider exploring further resources for advanced BST operations and optimizations.