JavaScript: Search for an Element in a Binary Search Tree

1. Introduction

A binary search tree (BST) is a binary tree where each node has a value, and the left subtree contains values less than the node's value, while the right subtree contains values greater than the node's value. Searching for an element in a BST is efficient as it reduces the problem size by half with every step.

2. Program Overview

In this program, we will create a BST and implement a search function to check if a specific element exists in the tree.

3. Code Program

// Define the structure for the tree node
function TreeNode(value) {
    this.value = value;
    this.left = null;
    this.right = null;
}

// Define the BST class
function BinarySearchTree() {
    this.root = null;
}

// Add a method to insert a new node
BinarySearchTree.prototype.insert = function(value) {
    var newNode = new TreeNode(value);
    if (!this.root) {
        this.root = newNode;
    } else {
        var current = this.root;
        while (true) {
            if (value < current.value) {
                if (!current.left) {
                    current.left = newNode;
                    break;
                }
                current = current.left;
            } else if (value > current.value) {
                if (!current.right) {
                    current.right = newNode;
                    break;
                }
                current = current.right;
            } else {
                // Duplicates are not allowed in this BST implementation
                break;
            }
        }
    }
};

// Add a method to search for a value
BinarySearchTree.prototype.search = function(value) {
    var current = this.root;
    while (current) {
        if (value === current.value) {
            return true;
        }
        if (value < current.value) {
            current = current.left;
        } else {
            current = current.right;
        }
    }
    return false;
};

// Create a new BST and insert some values
var bst = new BinarySearchTree();
bst.insert(5);
bst.insert(2);
bst.insert(8);
bst.insert(1);
bst.insert(3);

// Example usage
console.log(bst.search(3));  // true
console.log(bst.search(7));  // false

Output:

true
false

4. Step By Step Explanation

1. A TreeNode represents each node in the BST. It has a value, a left child, and a right child.

2. The BinarySearchTree class holds the root node and provides methods for insertion and search.

3. The insert method starts at the root and navigates down the tree to find the appropriate spot to place the new node.

4. The search method begins at the root and traverses down the tree. If it finds the value, it returns true. If it reaches a null node without finding the value, it returns false.

5. In our example, after inserting some values, we search for 3 (which is present) and 7 (which is not), resulting in the output of true and false respectively.