Hello Everyone,
Today I learn Binary Search Tree algorithm and in Javascript from freecodecamp and this is my first blog. So, I am writing this blog as a way to share what I learn and my knowledge in my way. Again It is not gonna be a professional way but more of a personal way.
Binary Search Tree or BST is a very famous data structure in programing world. In a professional way,
> BST is a collection of nodes arranged in a way where they maintain BST properties. Each node has a key and an associated value. While searching, the desired key is compared to the keys in BST and if found, the associated value is retrieved.
what I have understood, BST is a collection of nodes which contains number or data, we can find certain data by comparing all the data's to each other and if found the data or number get retrieved, it is very useful to find a certain data in a large collection or to sort a big messy collection data.
So I am now going to explain the code that I have written in javascript and show the code below:
BST has many function but for now let's explain add, remove, find/ isPresent, findMax, findMin.
First of all the Node class has a constructor which the the main node and the left and right node side of it. Then we declare the BST class which has has a construction and the root for now will be null.
Let's use add function. Add function first will declare the node variable to be the root. If the the node is empty then the Node class will add the data as first value. However if there is previous data there the current input data will be compare and if the data is lower then it will go to the next left node and and if the data is bigger then it will go to the next right node. We will use the recursion here until the data get settles unless the data is already presence then it will only return false.
findMin will return minimum and findMax will return Maximum value. As we know the left side node contain of any selected node will only be lower number, so the most left side node will be the most lowest number. It is same for right side node except the the right side will contain bigger number and the most right side will be biggest number. We will use white function until we find find the last number in findMin or findMax to find the minimum or maximum number
find or isPresent to find a certain value To check whether the BST contain certain number we can use find it by comparing the numbers or nodes with the input number or data. After comparing the number , if condition will decide whether the input data is lower or greater than current data, so that it can decide the correct path to reach the number. If the number is really present the that data will be return or it will return false/null. The difference between find and isPresent is find will return the number/node or null where isPresent will return true or false.
remove will return a value from BST To remove a node or data from BST we will rely on recursion. The first thing to check will be whether the BST is empty or not. If the data is found the next three condition will be checked,
- whether the selected node has any children or node
- Whether the selected node has no left/right children or node
- Whether the selected node has two children or node. For the first condition nothing needs to be done, for second condition replace the removed node with it's left/right node and for the third condition keep comparing the data with either side to set the nodes correct way, bigger will be right and lower will be left, A recursion is needed. But to start the whole function we will need to use recursion by calling the 'removeNode' (whatever you prefer) with two arguments, the first one will contain top node and second argument will contain the input code which we want to remove from BST
Here is the code:
`class Node {
constructor(data, left = null, right = null) {
this.data = data;
this.left = left;
this.right = right;
}
}
class BST {
constructor() {
this.root = null;
}
add(data) {
const node = this.root;
if (node === null) {
this.root = new Node(data);
return;
} else {
const searchTree = function(node) {
if (data < node.data) {
if (node.left === null) {
node.left = new Node(data);
return;
} else if (node.left !== null) {
return searchTree(node.left);
}
} else if (data > node.data) {
if (node.right === null) {
node.right = new Node(data);
return;
} else if (node.right !== null) {
return searchTree(node.right);
}
} else {
return null;
}
};
return searchTree(node);
}
}
findMin() {
let current = this.root;
while (current.left !== null) {
current = current.left;
}
return current.data;
}
findMax() {
let current = this.root;
while (current.right !== null) {
current = current.right;
}
return current.data;
}
find(data) {
let current = this.root;
while (current.data !== data) {
if (data < current.data) {
current = current.left;
} else {
current = current.right;
}
if (current === null) {
return null;
}
}
return current;
}
isPresent(data) {
let current = this.root;
while (current) {
if (data === current.data) {
return true;
}
if (data < current.data) {
current = current.left;
} else {
current = current.right;
}
}
return false;
}
remove(data) {
const removeNode = function(node, data) {
if (node == null) {
return null;
}
if (data == node.data) {
// node has no children
if (node.left == null && node.right == null) {
return null;
}
// node has no left child
if (node.left == null) {
return node.right;
}
// node has no right child
if (node.right == null) {
return node.left;
}
// node has two children
var tempNode = node.right;
while (tempNode.left !== null) {
tempNode = tempNode.left;
}
node.data = tempNode.data;
node.right = removeNode(node.right, tempNode.data);
return node;
} else if (data < node.data) {
node.left = removeNode(node.left, data);
return node;
} else {
node.right = removeNode(node.right, data);
return node;
}
}
this.root = removeNode(this.root, data);
}
}`
Again I wrote this blog to share with others developer and practice myself with this code. Give your opinion or link or any document that can help me to improve and understand better if you think there is any error with my understanding.
Top comments (0)