Binary Search Tree in Javascript

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.