BST in javascript
5 min readAug 23, 2019
Introduction
BST stands for binary search tree. It is a data structure & type of binary tree that allow us to store data in the ordered way. It can be used to search existence of number in
BST has following properties :
- All nodes of left subtree is always less than root node.
- All nodes of right subtree is always greater than root node.
- All subtree of the node also have the above two property.
e.g - Let’s say we have value : 8,3,10,1,14,6,7,4,13 then the BST represntation will be like this
In this article - I am going to explain how to write program for binary search tree in javascript and its traversal in different form.
Let’s Code
Let’s write code for adding elements to a BST -
class Node {
constructor(data) {
this.data = data;
this.left = this.right = null;
}
}class Bst {
constructor() {
this.root = null;
} add(data) {
const node = new Node(data);
if (this.root == null) {
this.root = node;
} else {
// the root variable below will be used to identify the root of the supplied value
let root = this.root;
while (root != null) {
//if data is less than root data, then it will be added to left
if (data < root.data) {
if (root.left == null) {
root.left = node;
root = null;
} else {
root = root.left;
}
}
// else data will be added to right
else {
if (root.right == null) {
root.right = node;
root = null;
} else {
root = root.right;
}
}
}
}
} addMultiple(...datas) {
datas.forEach(data => {
this.add(data);
})
}
}
const bst = new Bst();
bst.addMultiple(8, 3, 10, 1, 14, 6, 7, 4, 13);
The logic of the above code is -
- If root is null then assign the value as root
- If root is not null then find the node where this new data should be placed.
- If data is less than root value then it will be added to left else right. Check if root left/right is null or not : if null then add that element as left/right otherwise change the current root.
I understand that it can be little tricky and not clear, it was for me too when i picked it up again after three years of college 😬. But i will recommend you to write the code by yourself to understand it better. Once you have written, it will be much clear.
Now, let’s see how to traverse nodes
There are three types of traversal
- Inorder traversal- First traverse left node, second the root and then right node.
- Preorder traversal- First traverse root node, second the left and in last right.
- PostOrder traversal- First traverse left node , second the right node and in last root node.
Traversing is very easy, once you understood the binary tree. Let’s add traversing method to our Bst class.
class Node {
constructor(data) {
this.data = data;
this.left = this.right = null;
}
}
class Bst {
constructor() {
this.root = null;
} add(data) {
const node = new Node(data);
if (this.root == null) {
this.root = node;
} else {
// the root variable below will be used to identify the root of the supplied value
let root = this.root;
while (root != null) {
//if data is less than root data, then it will be added to left
if (data < root.data) {
if (root.left == null) {
root.left = node;
root = null;
} else {
root = root.left;
}
}
// else data will be added to right
else {
if (root.right == null) {
root.right = node;
root = null;
} else {
root = root.right;
}
}
}
}
} addMultiple(...datas) {
datas.forEach(data => {
this.add(data);
})
} inOrderTraverse() {
console.log("---traversing in order-----");
const traverse = (root) => {
if (root != null) {
traverse(root.left);
console.log(root.data);
traverse(root.right);
}
}
traverse(this.root);
} preOrderTraverse() {
console.log("---traversing pre order-----");
const traverse = (root) => {
if (root != null) {
console.log(root.data);
traverse(root.left);
traverse(root.right);
}
}
traverse(this.root);
} postOrderTraverse() {
console.log("---traversing post order-----");
const traverse = (root) => {
if (root != null) {
traverse(root.left);
traverse(root.right);
console.log(root.data);
}
}
traverse(this.root);
}
}
const bst = new Bst();
bst.addMultiple(8, 3, 10, 1, 14, 6, 7, 4, 13);
bst.inOrderTraverse();
bst.preOrderTraverse();
bst.postOrderTraverse();
IsExist value
class Node {
constructor(value) {
this.data = value;
this.left = null;
this.right = null;
}
}class BST {
constructor() {
this.root = null;
} isExist(value) {
let root = this.root;
while (root != null) {
if (root.data == value) {
return true;
}
if (value < root.left) {
root = root.left;
}
else {
root = root.right;
}
}
return false;
} add(value) {
const node = new Node(value);
if (this.root == null) {
this.root = node;
}
else {
let root = this.root;
while (root != null) {
if (value < root.data) {
if (root.left == null) {
root.left = node;
root = null;
}
else {
root = root.left;
}
}
else {
if (root.right == null) {
root.right = node;
root = null;
}
else {
root = root.right;
}
}
}
}
}}const bst = new BST();
bst.add(5);
bst.add(51);
bst.add(50);console.log(bst.isExist(5));
console.log(bst.isExist(51));
Remove value
class Node {
constructor(value) {
this.data = value;
this.left = null;
this.right = null;
}
}class BST {
constructor() {
this.root = null;
} isExist(value) {
let root = this.root;
while (root != null) {
if (root.data == value) {
return true;
}
if (value < root.left) {
root = root.left;
}
else {
root = root.right;
}
}
return false;
} add(value) {
const node = new Node(value);
if (this.root == null) {
this.root = node;
}
else {
let root = this.root;
while (root != null) {
if (value < root.data) {
if (root.left == null) {
root.left = node;
root = null;
}
else {
root = root.left;
}
}
else {
if (root.right == null) {
root.right = node;
root = null;
}
else {
root = root.right;
}
}
}
}
} remove(value) {
let root = this.root;
while (root != null) {
if (root.data === value) {
if (root.left && root.right) {
const right = root.right;
delete root.right;
Object.assign(root, right);
}
else if (root.left) {
const left = root.left;
delete root.left;
Object.assign(root, left);
}
else if (root.right) {
const right = root.right;
delete root.right;
Object.assign(root, right);
}
else {
delete root.data;
}
return;
}
root = value < root.data ? root.left : root.right;
}
}}const bst = new BST();
bst.add(5);
bst.add(51);
bst.add(50);bst.remove(5);console.log(bst.isExist(5));
console.log(bst.isExist(51));
This is the end of the article guys. Hope you are able to understand.
