JavaScript Program to Implement a Binary Search Tree (BST)

Introduction

A Binary Search Tree (BST) is a data structure where each node has at most two children, and for any given node:

• The left subtree contains nodes with values less than the node's value.
• The right subtree contains nodes with values greater than the node's value.

BSTs are widely used because they allow efficient insertion, search, and deletion operations, with an average time complexity of O(log n).

This guide will walk you through writing a JavaScript program to implement a Binary Search Tree, supporting common operations like insertion, search, and in-order traversal.

Problem Statement

Create a JavaScript program that:

• Implements a Binary Search Tree (BST).
• Supports operations like:
  • Insertion of nodes.
  • Searching for a specific node.
  • In-order traversal (left-root-right traversal).

Example:

• Input: Insert nodes 50, 30, 70, 20, 40, 60, 80
• Output (In-order Traversal): 20 30 40 50 60 70 80

Solution Steps

1. Define a Node Class: Create a Node class to represent each node in the tree.
2. Define a Binary Search Tree (BST) Class: Implement methods for:
   • Insert: Adds a node to the BST.
   • Search: Finds a node with a specific value.
   • In-order Traversal: Traverses the BST in sorted order.
3. Display the Tree: Perform in-order traversal to print the sorted nodes.

JavaScript Program

Step 1: Define the Node Class

// JavaScript Program to Implement a Binary Search Tree (BST)
// Author: https://www.rameshfadatare.com/

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

Step 2: Define the Binary Search Tree (BST) Class

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

    // Insert a node into the BST
    insert(value) {
        const newNode = new Node(value);

        // If the tree is empty, set the root to the new node
        if (this.root === null) {
            this.root = newNode;
        } else {
            this.insertNode(this.root, newNode);
        }
    }

    // Helper function to insert a node recursively
    insertNode(currentNode, newNode) {
        if (newNode.value < currentNode.value) {
            // Left subtree
            if (currentNode.left === null) {
                currentNode.left = newNode;
            } else {
                this.insertNode(currentNode.left, newNode);
            }
        } else {
            // Right subtree
            if (currentNode.right === null) {
                currentNode.right = newNode;
            } else {
                this.insertNode(currentNode.right, newNode);
            }
        }
    }

    // Search for a node with a given value
    search(value) {
        return this.searchNode(this.root, value);
    }

    // Helper function to search recursively
    searchNode(currentNode, value) {
        if (currentNode === null) {
            return null; // Node not found
        }
        if (value < currentNode.value) {
            return this.searchNode(currentNode.left, value);
        } else if (value > currentNode.value) {
            return this.searchNode(currentNode.right, value);
        } else {
            return currentNode; // Node found
        }
    }

    // In-order traversal (left-root-right) to print nodes in sorted order
    inOrderTraversal() {
        this.inOrderTraversalNode(this.root);
    }

    // Helper function to perform in-order traversal
    inOrderTraversalNode(currentNode) {
        if (currentNode !== null) {
            this.inOrderTraversalNode(currentNode.left);
            console.log(currentNode.value);
            this.inOrderTraversalNode(currentNode.right);
        }
    }
}

Step 3: Example Usage

// Example usage of the Binary Search Tree
const bst = new BinarySearchTree();
bst.insert(50);
bst.insert(30);
bst.insert(70);
bst.insert(20);
bst.insert(40);
bst.insert(60);
bst.insert(80);

console.log("In-order Traversal:");
bst.inOrderTraversal(); // Output: 20 30 40 50 60 70 80

// Search for a specific node
const foundNode = bst.search(60);
if (foundNode !== null) {
    console.log(`Node ${foundNode.value} found in the BST`);
} else {
    console.log("Node not found in the BST");
}

Output Example

In-order Traversal:
20
30
40
50
60
70
80
Node 60 found in the BST

Explanation

Step 1: Define the Node Class

• The Node class represents each node in the binary search tree. Each node has:
  • value: The value stored in the node.
  • left: A reference to the left child node.
  • right: A reference to the right child node.

Step 2: Define the Binary Search Tree Class

• Insert: The insert() method adds nodes to the BST. If the tree is empty, the new node becomes the root. Otherwise, the insertNode() function is used to recursively find the appropriate position for the new node based on its value.
• Search: The search() method looks for a node with a given value. It traverses the tree, comparing the target value to each node's value, and returns the node if found.
• In-order Traversal: The inOrderTraversal() method prints the values of the nodes in sorted order by recursively visiting the left subtree, the root, and then the right subtree.

Step 3: Example Usage

• The BST is created, and nodes are inserted in an arbitrary order.
• An in-order traversal is performed, which prints the nodes in sorted order.
• The search() function checks for the presence of a specific node in the tree.

Conclusion

This JavaScript program demonstrates how to implement a Binary Search Tree (BST) with operations for insertion, searching, and in-order traversal. A BST is an efficient data structure for storing sorted data and allows for quick lookups, insertions, and deletions, making it a useful tool for many algorithms and applications.