JavaScript: Search for an Element in a Binary Search Tree

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
// 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 (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
        }
    }
}

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 {
    console.log("Node not found in the BST");
}

// 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 {
    console.log("Node not found in the BST");

Output Example

Node 60 found in the BST
Node not 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.