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 ]
Top comments (0)