Introduction

A Binary Search Tree (BST) is a data structure that stores elements in a way that enables efficient searching, insertion, and deletion. In a BST:

• The value of every node in the left subtree is less than the value of the node itself.
• The value of every node in the right subtree is greater than the value of the node itself.

The search operation in a BST takes advantage of this property. Starting from the root, you can decide to move left or right based on whether the target value is less than or greater than the current node’s value.

This guide will walk you through writing a JavaScript program to search for an element in a BST.

Problem Statement

Create a JavaScript program that:

• Implements a Binary Search Tree (BST).
• Searches for a given element in the BST.
• Returns the node if found, otherwise returns `null`.

Example:

• Input: BST with nodes `50, 30, 20, 40, 70, 60, 80`, search for `60`

• Output: `Node 60 found in the BST`

• Input: BST with nodes `50, 30, 20, 40, 70, 60, 80`, search for `25`

• Output: `Node not found in the BST`

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:
• Insertion of nodes.
• Searching for a specific node.
3. Search Operation:
• Starting from the root, compare the target value with the current node.
• Traverse left or right depending on whether the target is less than or greater than the current node’s value.

JavaScript Program

Step 1: Define the Node Class

``````// JavaScript Program to Search for an Element in a Binary Search Tree

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 (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) {
}
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
}
}
}
``````

Step 3: Example Usage

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

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

// Search for a node that doesn't exist
const notFoundNode = bst.search(25);
if (notFoundNode !== null) {
console.log(`Node \${notFoundNode.value} found in the BST`);
} else {
``````

Output Example

``````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 finds a node with the specified value. It compares the value with the current node:
• If the value is less than the current node, it recursively searches the left subtree.
• If the value is greater, it searches the right subtree.
• If the value matches, the node is found.
• If the search reaches a `null` node, the value does not exist in the tree.

Step 3: Example Usage

• A Binary Search Tree is created with several values inserted into it.
• The `search()` method is used to find the node with the value `60` and the node `25`, which doesn't exist.

Time Complexity

• Best Case: O(log n), where `n` is the number of nodes (in a balanced tree).
• Worst Case: O(n) when the tree becomes unbalanced (e.g., all nodes are inserted in sorted order, resulting in a degenerate tree).

Conclusion

This JavaScript program demonstrates how to search for an element in a Binary Search Tree (BST) by utilizing the tree's inherent properties. The program efficiently performs insertion and search operations, providing a fast and structured way to manage data. This algorithm is a great introduction to understanding tree-based data structures and recursion.