Binary Search Tree in Javascript

Binary Search Tree is node based data structure which has the below properties

1. Left Nodes of tree is lesser than its parent node.
2. Right Nodes of tree are greater than its parent node.
3. The left and right subtree should be binary search tree.

Create Binary Search Tree in Javascript

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

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

    insert(value) {
        let newNode = new Node(value);
        if (this.root == null) {
            this.root = newNode;
        } else {
            let currentNode = this.root;
            while (true) {
                if (value < currentNode.value) {
                    if (!currentNode.left) {
                        currentNode.left = newNode;
                        return this;
                    }
                    currentNode = currentNode.left;
                } else {
                    if (value > currentNode.value) {
                        if (!currentNode.right) {
                            currentNode.right = newNode;
                            return this;
                        }
                        currentNode = currentNode.right;
                    }
                }
            }
        }
    }
}

const tree = new BinaryTree();
tree.insert(9)
tree.insert(4)
tree.insert(6)
tree.insert(20)
tree.insert(170)
tree.insert(15)
tree.insert(1)

console.log(tree)

Searching a Node in Binary Search Tree

Lets discuss program to search a node in BST. Lets see code snippet first.

search(value) {
        let currentNode = this.root;

        while (currentNode) {
            if (currentNode.value == value)
                return currentNode;

            if (value < currentNode.value) {
                currentNode = currentNode.left;
            } else {
                currentNode = currentNode.right;
            }

        }
    }

For searching a value in BST we will compare it with the parent node and if it doesn’t matched with parent node, we will check left tree if its less than parent node or right tree if greater than parent node.

Time Complexity : O(logn n)

Find Height of Binary Search Tree

For height of a BST we will recursively find the length of left binary tree and right binary tree. The maximum value between height of left tree and right tree from parent will be consider as height of tree.

Lets check the below program for that.

height(node = this.root) {

        if (node == null)
            return 0;
        else {
            let lHeight = this.height(node.left);
            let rHeight = this.height(node.right);

            if (lHeight > rHeight)
                return (lHeight + 1);
            else
                return (rHeight + 1);
        }
    }

Reference :

https://www.geeksforgeeks.org/implementation-binary-search-tree-javascript/

RELATED POST

Node JS : How require(); works Edit Distance program in Javascript Binary Search Program in Javascript Create Linked List and Remove node in Javascript Find middle element in Linked List in Javascript