Your Web News in One Place

Help Webnuz

Referal links:

Sign up for GreenGeeks web hosting
May 20, 2022 11:06 am GMT

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 nodeTree.contains(2);console.log("Root",Tree.root);console.log("Printing tree Inorder [Left, Root, Right]");// 2,5,10,10,20Tree.printTreeInOrder()//@todo - test properlyconsole.log("Printing tree Preorder [Root, Left, Right]");Tree.printTreePreOrder();console.log("Printing tree Postorder [Left, Right, Root]");Tree.printTreePostOrder();

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]


Original Link: https://dev.to/rajeshroyal/implement-binary-search-tree-in-javascript-simplest-possible-1pm1

Share this article:    Share on Facebook
View Full Article

Dev To

An online community for sharing and discovering great ideas, having debates, and making friends

More About this Source Visit Dev To