Hi esteemed readers, what if i told you DATA STRUCTURES IS SIMPLE AND FUN. 😎yes i said that in a capital letter way.
Well lets talk about 'TREES' in this episode of data structure, and your requests are welcome on any data structure topic you would love me to talk about.
Alright Tyler
Trees is a non-linear and hierarchical data structure consisting of nodes, each nodes has a value and a left and right children. this children nodes are the immediate successor of a node.
The node with the value of 48 can be referred to as the root node. A root node does not have any parent, always the topmost node and a path to all other nodes. Now the silbings [children of the same parent node] the silbings node can also have their children, lets see an example;
well🤔 with the children of the root node having thier own children, our little tree seems to be growing 😁 this is what a perfect binary tree does, They double as they grow, below is a representatation.
1 ^ 2
2 ^ 4
4 ^ 8
8 ^ 16 ...... and so on as big as we want.
Lets Take Look At How Big Our Tree Has Become Once Again
Wow, not bad i guess.. Lets say this is the end of our tree, the bottom nodes would be referred to as the leaf nodes because it has no children node.
LETS MOVE TO BST (Binary Search Tree)
The main focus of this article is to actually talk about Binary Search Trees and build one using javascript.
Binary Search Tree is the most common tree data structure and a subset of binary tree that we have talked about. its really good for searching and comparing things. when it comes to BST, the rules are
A value that is lesser than the root node or parent node goes to the left side of that node
And also a value greater than the root node or parent goes to right side of that node
Lets take a look at an example to better understand
And then the second rule is a node can only have up to 2 children
To better understand this, you can play around with this tool visualgo.net/en/bst .
Alright guys ..lets build our first Binary Search Tree. Let's Go Coding
Today i will only be implementing the insert , so first we have to create a node that has a value and a left and right children.
For you to insert something , you need to have the object you want to insert right?? so thats basically what we have done here. Created a node that we would be adding to our root node.
class node{
constructor(value){
this.value = value;
this.left = null;
this.right = null;
}
}
Lets also create our root node 😎
class BST{
constructor(){
this.root = null;
}
}
Now that we have our root node with the value of null, lets now also write our insert. we are going to place the insert inside our BST class but before we fully do that lets break this thing into chunks so it doesn't look bulky and confusing.
SHALL WE !??
class BST{
constructor(){
this.root = null;
}
insert(value){
const newnode = new node(value);
if(this.root == null){
this.root = newnode;
}
In this block of code we pass an empty node into the insert class
Then we check if our this.root is == null , if the root is empty then our root equals the value we would be passing in the node we created.
insert(value){
const newnode = new node(value);
if(this.root == null){
this.root = newnode;
}else{
let current = this.root;
//So While The Above Statement Is True
while (true){
// So We Make A Check
if (value < current.value){
//So We Make Our First Check Here
if(!current.left ){
//If There Is No Left Node In Current Then...
current.left = newnode;
return this
}
current = current.left
}
else we created a variable to store our root if we have one.
Making our first check
If insert value is less than the value of our root node{ current.value}
if this is true, check if there is no value on the left then set the newnode to current.left and return the BST class. ESLE shift the current variable and run the above code again
else{
/* We Do The Same For Right */
if(value > current.value){
if(!current.right){
current.right = newnode;
return this
}
current = current.right
}
And vice versa for the right children
And then we instanstiate and call our class
let CallBst = new BST();
CallBst.insert(9)
CallBst.insert(32)
console.log(CallBst)
I'm just going to paste the chunks here so you can better see how they come together
class BST{
constructor(){
this.root = null;
}
insert(value){
const newnode = new node(value);
if(this.root == null){
this.root = newnode;
}else{
let current = this.root;
//So While The Above Statement Is True
while (true){
if (value < current.value){
// First Check
if(!current.left ){
//If There Is No Left Node In Current Then...
current.left = newnode;
return this
}
current = current.left
}else{
if(value > current.value){
if(!current.right){
current.right = newnode;
return this
}
current = current.right
}
}
}
}
}
}
let CallBst = new BST();
CallBst.insert(9)
CallBst.insert(32)
console.log(CallBst)
I believe you will now agree with me that Data Structure is fun and simple😎 .
Was My Article Helpful?? if yes please drop comment below as this would motivate me and also look out for the rest of this artlcle and more on data structures.