Binary Search Tree in Javascript

anuj singh — Thu, 08 Aug 2024 17:03:09 +0000

Implementing a Binary Search Tree in JavaScript

In this post, we’ll explore how to implement a basic Binary Search Tree (BST) in JavaScript. We’ll cover inserting nodes and performing different tree traversal methods—in-order, pre-order, and post-order.

The Node Class
First, let’s define a Node class to represent each node in the tree:

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

Each Node object has three properties:

value: The data stored in the node.
left: A pointer to the left child node.
right: A pointer to the right child node.

The BinarySearchTree Class

Next, we’ll define a BinarySearchTree class that will manage the nodes and provide methods to interact with the tree:

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

    isEmpty() {
        return this.root === null;
    }

    insertNode(root, newNode) {
        if(newNode.value < root.value) {
            if(root.left === null) {
                root.left = newNode;
            } else {
                this.insertNode(root.left, newNode);
            }
        } else {
            if(root.right === null) {
                root.right = newNode;
            } else {
                this.insertNode(root.right, newNode);
            }
        }
    }

    search(root, value) {
        if(!root) {
            return false;
        }
        if(root.value === value) {
            return true;
        } else if(root.value > value) {
            return this.search(root.left, value);
        } else {
            return this.search(root.right, value);
        }
    }

    insert(value) {
        const newNode = new Node(value);
        if(this.isEmpty()) {
            this.root = newNode;
        } else {
            this.insertNode(this.root, newNode);
        }
    }
}

Key Methods:

isEmpty(): Checks if the tree is empty.
insertNode(root, newNode): Inserts a new node into the tree, maintaining the binary search tree property.
search(root, value): Recursively searches for a value in the tree.
insert(value): A convenient method to insert a new value into the tree.

Tree Traversal Methods

Once we have a tree, we often need to traverse it. Here are the three common traversal methods:

In-order Traversal

In-order traversal visits the nodes in the following order: Left, Root, Right.

inOrder(root) {
    if(root) {
        this.inOrder(root.left);
        console.log(root.value);
        this.inOrder(root.right);
    }
}

This traversal prints the nodes in non-decreasing order for a binary search tree.

Pre-order Traversal

Pre-order traversal visits the nodes in the following order: Root, Left, Right.

preOrder(root) {
    if(root) {
        console.log(root.value);
        this.preOrder(root.left);
        this.preOrder(root.right);
    }
}

This traversal is useful for copying the tree structure.

Post-order Traversal

Post-order traversal visits the nodes in the following order: Left, Right, Root.

postOrder(root) {
    if(root) {
        this.postOrder(root.left);
        this.postOrder(root.right);
        console.log(root.value);
    }
}

This traversal is often used for deleting or freeing nodes.

Example Usage

Let’s see how these methods work together:

const bst = new BinarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(20);
bst.insert(3);
bst.insert(7);

console.log('In-order Traversal:');
bst.inOrder(bst.root);

console.log('Pre-order Traversal:');
bst.preOrder(bst.root);

console.log('Post-order Traversal:');
bst.postOrder(bst.root);

Conclusion

With this implementation, you can now create and interact with a Binary Search Tree in JavaScript. Understanding tree structures and traversal methods is crucial for many algorithmic problems, especially in areas like search algorithms, parsing expressions, and managing hierarchical data.

DEV Community: anuj singh

Binary Search Tree in Javascript

Implementing a Binary Search Tree in JavaScript