DEV Community

Cover image for Implement binary search tree in JavaScript - simplest possible.
Rajesh Royal
Rajesh Royal

Posted on

Implement binary search tree in JavaScript - simplest possible.

Here is a simplest Implementation of the binary search tree, with JavaScript classes.

⚠ The tree will be unbalanced when Input is incremental [ex - 1,2,3,4,5 ..... n]

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

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

    // insert a new node in tree
    insertNode(data) {
        if (this.root === null) {
            this.root = new Node(data);
            return;
        }
        let currentChildren = this.root;
        this.findNodeToInsert(data, currentChildren);
    }
    findNodeToInsert(data, parentNode) {
        if (data > parentNode.data) {
            if (parentNode.right) {
                this.findNodeToInsert(data, parentNode.right);
                return;
            }
            parentNode.right = new Node(data);
        }
        else if (data <= parentNode.data) {
            if (parentNode.left) {
                this.findNodeToInsert(data, parentNode.left);
                return;
            }
            parentNode.left = new Node(data);
        }

    }

    // search a node in tree
    contains(data, currentNode = this.root) {
        // using ? operator to safegurad when we hit the null node 

        if (!this.root) return null;

        if (data === currentNode?.data) {
            console.log('Contains', currentNode)
            return currentNode;
        }

        if (data > currentNode?.data) {
            this.contains(data, currentNode?.right);
        } else if (data < currentNode?.data) {
            this.contains(data, currentNode?.left)
        } else {
            console.log("Node dosen't contain to this tree");
            return null;
        }
    }

    // print binary tree 
    printTreeInOrder(currentNode = this.root) {
        if (!this.root || !currentNode) return;
        this.printTreeInOrder(currentNode?.left)
        console.log(currentNode.data);
       this.printTreeInOrder(currentNode?.right);
    }
    printTreePreOrder(currentNode = this.root) {
        if (!this.root || !currentNode) return;
        console.log(currentNode.data);
        this.printTreeInOrder(currentNode?.left)
       this.printTreeInOrder(currentNode?.right);
    }
    printTreePostOrder(currentNode = this.root) {
        if (!this.root || !currentNode) return;
        this.printTreeInOrder(currentNode?.left)
        this.printTreeInOrder(currentNode?.right);
        console.log(currentNode.data);
    }
}

const Tree = new BinarySearchTree();

Tree.insertNode(2);
Tree.insertNode(5);
Tree.insertNode(10);
Tree.insertNode(10)
Tree.insertNode(20)

// search a node
Tree.contains(2);

console.log("Root",Tree.root);

console.log("Printing tree Inorder [Left, Root, Right]");
// 2,5,10,10,20
Tree.printTreeInOrder()

//@todo - test properly
console.log("Printing tree Preorder [Root, Left, Right]");
Tree.printTreePreOrder();

console.log("Printing tree Postorder [Left, Right, Root]");
Tree.printTreePostOrder();
Enter fullscreen mode Exit fullscreen mode

Its a very simple implementation of the binary search tree. There can be some edge cases.

P.S. - I make my blog covers from - https://coverview.vercel.app/ [with customization]
👋

Discussion (0)