JavaScript: Implement a Binary Search Tree

1. Introduction

A Binary Search Tree (BST) is a binary tree where each node has at most two children, referred to as the left and right child. For each node, all elements in the left subtree are less than the node, and all elements in the right subtree are greater than the node. In this guide, we'll illustrate how to create a basic Binary Search Tree (BST) in JavaScript.

2. Program Overview

1. Define the Node class to represent individual nodes in the BST.

2. Define the BinarySearchTree class which includes methods: insert, find, and contains.

3. Demonstrate BST operations using an example.

3. Code Program

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

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

    // Function to insert a value into the BST
    insert(value) {
        let newNode = new Node(value);
        if (!this.root) {
            this.root = newNode;
            return this;
        }
        let current = this.root;
        while (true) {
            if (value === current.value) return undefined; // No duplicates allowed
            if (value < current.value) {
                if (!current.left) {
                    current.left = newNode;
                    return this;
                }
                current = current.left;
            } else {
                if (!current.right) {
                    current.right = newNode;
                    return this;
                }
                current = current.right;
            }
        }
    }

    // Function to check if a value exists in the BST
    contains(value) {
        if (!this.root) return false;
        let current = this.root;
        let found = false;
        while (current && !found) {
            if (value < current.value) {
                current = current.left;
            } else if (value > current.value) {
                current = current.right;
            } else {
                found = true;
            }
        }
        return found;
    }
}

// Create an instance of the BinarySearchTree
const tree = new BinarySearchTree();

// Insert values into the BST
tree.insert(10);
tree.insert(6);
tree.insert(15);
tree.insert(3);
tree.insert(8);
tree.insert(20);

// Search for a value in the BST
console.log(tree.contains(8));  // true
console.log(tree.contains(50)); // false

4. Step By Step Explanation

1. Node Class: Represents individual elements in the BST. Each node contains a value, a left child, and a right child.

2. BinarySearchTree Class:

- The BST is initialized with a root set to null.

- The insert method is employed to add a new value. If the BST is empty, the new value becomes the root. Otherwise, it traverses the tree to find the appropriate location for the new node.

- The contains method checks if a given value is present in the BST.

3. Example: After creating a BST instance, we insert values to form the tree. The tree structure looks like this:

       10
      /  \
     6    15
    / \     \
   3   8     20

Our search confirms that 8 is present and 50 is not in our BST. 

Binary Search Trees are an essential data structure in computer science due to their efficiency in searching, inserting, and deleting operations. This basic JavaScript implementation offers a foundational understanding of BSTs.