Implementing Binary Search Tree in Javascript

Binary Search Tree is one of the most important and commonly used data structure. It is very helpful in storing and searching items in less time complexity.

Insertion Time : O(logn)
Deletion Time : O(logn)
Searching Time : O(logn)

Note: These time complexities are only applicable for binary search trees that are not degenerate. That is, the tree should not be skewd in one direction.

In this blog, I will explain how to implement BST in Javascript.

First of all, let's breakdown the components of a BST

Node
Root
Leaves
Left child
Right child

Features of Binary Search Trees

The left child has a value always less than its parent.
The right child has a value always greater than its parent.
The inorder traversal of a BST gives the elements in sorted order.

To mimic the Node, we have to make a class call Node

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

We have our node, now we have to attach new nodes as a left child or right child.

function addNode(root,val){
    if(root===null){
        return new Node(val)
    }    
    if(root.val<val)
        root.right=addNode(root.right,val)
    else
        root.left=addNode(root.left,val)
    return root
}

To check if our implementation is correct, we will do inorder traversal. If the output is in sorted order that means it is correct.

function inorder(root,inorderItems){
    if(root===null)
        return 
    inorder(root.left,inorderItems)
    inorderItems.push(root.val)
    inorder(root.right,inorderItems)
}

Now, let's see the full code

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



function addNode(root,val){
    if(root===null){
        return new Node(val)
    }    
    if(root.val<val)
        root.right=addNode(root.right,val)
    else
        root.left=addNode(root.left,val)
    return root
}

function inorder(root,inorderItems){
    if(root===null)
        return 
    inorder(root.left,inorderItems)
    inorderItems.push(root.val)
    inorder(root.right,inorderItems)
}

let items = [3,4,1,2,7,-3]
let inorderItems = []
let root = new Node(items[0])

for(let i=1;i<items.length;++i){
    root = addNode(root,items[i])
}
inorder(root,inorderItems)
console.log(inorderItems) // [ -3, 1, 2, 3, 4, 7 ]

Blog

Implementing Binary Search Tree in Javascript

Rudra Pratap

Join Our Newsletter. No Spam, Only the good stuff.

Related