How To Implement Binary Search Tree In Javascript - letsbug

     Many times we required to have more than two paths from data object (non-linear) when we have to represent one or many relationship. The best way is to use non-linear data structure.

    Tree is a non-linear data structure. Non-linear  data structures are capable of expression more complex relationship than linear data structure. In general, wherever the hierarchical relationship among data is to be preserved tree is used.

    Today in this article we are going to implement a basic Binary Search Tree. But before that lets see a binary tree.

    What is a Binary Tree?

    Binary Tree is a special form of a tree is finite set of nodes, which is either empty or partitioned into three sets, one which is the root and two disjoint binary trees called left subtree and right subtree. It si a tree where every node can have at most two branches(children).

    Now lets implement 

Binary Search Tree in Javascript

First we create BinaryTree class which encapsulates our whole tree. And has all the main methods of the tree. We have only implemented two methods insert and traverse.

class BinaryTree{
    constructor(){
        this.root = null
    }
    insert(data){
        if(this.root == null){
            this.root = new Node(data)
        }else{
            this.root.addNode(new Node(data))
        }
    }
    traverse(){
        this.root.traverse()
    }
}

Then we have Node class which is the core of the BinaryTree class. All the data added into the tree is stored as a node into the BinaryTree. addNode and traverse are two methods of the Node class.

class Node{
    constructor(data){
        this.left = null
        this.right = null
        this.value = data
    }
    addNode(node){
        if(node.value < this.value){
            if(this.left == null){
                this.left = node
            }else{
                this.left.addNode(node)
            }
        }else if (node.value > this.value){
            if(this.right == null){
                this.right = node
            }else{
                this.right.addNode(node)
            }
        }
    }
    traverse(){
        if(this.left != null) this.left.traverse()
        console.log(this.value)
        if(this.right != null) this.right.traverse()
    }
}

Now that we have our classes done. Below we initialise binary tree as tree and add random number elements into it. And then we call the traverse method and print the tree.

let tree = new BinaryTree()
for(let i = 0; i < 20; i++){
    tree.insert(Math.ceil(Math.random(1) * 200))
}
tree.traverse()
console.log(tree)

Below is how we get the output.

3

6

21

34

60

63

73

78

105

113

140

143

148

156

172

175

189

196

BinaryTree {

  root: Node {

    left: Node { left: null, right: null, value: 3 },

    right: Node { left: [Node], right: null,

value: 196 },

    value: 6

  }

}

Thankyou