Hi, I'm Beau in this video
I will be going over some common data structures and algorithms in JavaScript
I'll be showing you how to implement them in JavaScript
So if you want to see the exact list
You can check the description and I have links to all the code in the description as well. So let's get started
A stack of books is a great example of the stack data structure
If you make a stack of books
The topmost book in the stack was the one that you put there last if you remove that book from your stack stop
You would expose the book that was put there before
The last book stacks are of last in first out type of service
The last book you put on top of a stack would be the first book
You take off the stack. Another example of the stack is your browsers back button. If you look up here, we just opened up facebook.com
So we add it to the top of the stack of sites that we've already visited previously
Would you stack top push push is one of the stack methods you push Facebook on top of the stack?
This middle is what it looks like when we are
Visiting Facebook and then this bottom image is where we press the back button to navigate back to Twitter
So we pop off the most recent URL and we just leave Twitter at the top of it
The function is traditionally provided in the stack our push
for placing data onto a stack
pop for removing the top element of a stack
peak for displaying the top element of a stack and
length or size
for determining how many elements are on a stack a
Nice feature of JavaScript. Is that the array?
object
Already has all the functions we need in order to use it as a stack so you could just use an array as a stack
I will show you how to do this using an array
But then I will actually create a stack class and show you how that works, too
I'm going to use an array stack to find words that are palindromes a
Palindrome is a word that is spelled the same forwards and backwards such as Bob b.o.b. Or racecar
RAC eca are
okay, so we have our letters equals an empty array and
That's the stack
Because remember I said arrays are have all the functions of a stack. So look at how this program works first
we're gonna set a word to be anywhere we want and we're gonna choose race car, which is a palindrome and
Then we are going to have a variable which is just a empty string for our word or first word
We're going to use the stack to fill up the r-word variable with the reverse of the word variable
The first thing we're going to do is put the letters of the word into the stack
So we have a for loop here and we're going to start at
Index 0 and go to the last index of the word length
So an index in a string is just which character we're looking at
so we're going to do letters which remember is our stack dot put
The step function where you put something on top of the stack and we're going to push word
Index I so that's just going to take
This for loop is just going to take each
Letter of our word because we have an X 0 and X 1 and X 2 each letters new index and push it on
to the letter stack
Now we're going to pop off the stack in reverse order so we can create the r-word
variable which is the reverse of the word variable another for loop and
Now we are going to have the R word and we're going to add one letter at a time from the stack by
popping off the top letter and
Because they were put in order they're going to be popped off in reversed order
Now we have a string that should be the reverse of the first word
So word and our words to be reverse of each other now to check it's a palindrome
We just say if our word equals equals equals word. It is a palindrome
Over else it's not a palindrome. So let's run that and see what happens and
Racecard is a palindrome
but if we change that to
Free code yeah and run that
Nope, it's not a palindrome
Okay, that was just a basic usage of a stack using an array now. I will show you how to implement a stack in
JavaScript so you can understand stacks a little more
You probably would never do that because you can use an array as a staff, but this should possibly help you understand
How stacks work a little better
So here's where we're going to create the stack, which is going to be this function here
We're going to have two variables this that count
and this that storage now this storage is an empty object and
Count is gonna keep track of how many items are in the stack
So here are all the different methods
We have pushed this step push is going to add a value to the end of the stack
You're gonna pass end the value this that storage or storage is the empty object
At the end X this that count we are going to add the value
so we're gonna put the value on the top of the stack or the end of the stack and then we're just going to increment
Count up one so now it's showing that we have another item in the stack the next function
We're going to remove and return the value at the end of the stack or at the top of the stack
Which is the stuff top this is gonna pop an item off
So if this that count equals equals zero
That means there's nothing of the stack and we're going to return undefined because there is nothing in the stack once we return undefined
right
We're not gonna do anything it the rest of this code here because we've already returned from this function if we're popping off something
We're going to have to decrement the count. So it's a count minus one
So one less we're gonna set the result to this that storage which is the object for our stack and index this count
which is the last item in the stack and
Then we're going to delete that item and we're gonna return result. So you get the last item back
but it will be deleted off of the stack and
there's just a few more methods this dot size is
going to return this that count which is the number of items in the stack and
then the last
function is
This that peak which is going to return the value at the end of the stack
But it will not
Remove it like pop so peek and pop are kind of similar but pop removes the item and peek does not remove the item
So return this dot storage and then this that count minus one
This that count would actually be they'll index one after the final item because what that's where you would add in a new item
But you would have to do minus 1 to get the last item
And if you're peeking you do not want to pass in the value, so let me take that bad off there
So you only pass in the value when you're pushing in something
Let's see how this would work down here
Okay, we are going to create a variable called my stack which is a new stack which is what we just defined up there
We're gonna push one on to it to the top. Don't push two on the top
so it's just a stack with one and then two we're going to
Peak and we're gonna have to console dot log this because it's going to just return
The top number of the staff which should be two now, we're gonna pop off to so it's going to return to again
But it's gonna remove it and if we peek will she be back to one?
And before we run that I forgot these extra parentheses here
Because these are functions and need the parentheses at the end of all functions. So let's try that
Okay, see we peaked at two we popped off two and then when we peaked again
It was one because two was was removed. Now. You can also add other things to the stack
Now I'm going to push a string onto the stack and we're going to check the size then want a peak and
I'm gonna pop it off anyway a peak again. So let's see what that does
So we push the one we push to
Repeat with show two we pop whoosh pop off, too
we peaked again which showed one so there's only one thing in the stack then we
pushed free code camp to string and we
Console dot log the size and now this item to the stack is just one on
The bottom and then free code camp on the top
We're going to peak which is going to show free coke camp now. We're going to pop
Which is going to pop off and show freako camp and they're gonna peak again and we'll see that it's just one on the bottom
Well, those are the basics of stack
The set data structure is kind of like an array
except there are no duplicate items and the values are not in any particular order the
Typical use first set is to simply check for the presence of an item
I'm going to show you how to implement a set function bf6 actually has a built in set object
however, the built in set objects does not contain all the methods that are
Common to sets so you may still have to implement part of the set yourself
Depending on what you're gonna use it for when I show you the implementation for the set
I will tell you which methods are part of the es6 set and which are not so we're just gonna go through this code
We're gonna call it my set. Now we could call it set but I want to make it different than the es6 set
So this is my set. So here's just the collection
This set is gonna be a collection of items and we're gonna store them in an array which an array can't have duplicate items
But we're gonna implement this in such a way that you cannot add duplicate items to this array this method the method
Has is gonna check for the presence of an element and then return true or false
So you have passed in the element and it's going to do collection that index of element is
Not negative one. So if the element is not in the collection, it's gonna return negative one. So if it doesn't
Return negative one. It's true. So if it's not negative one, it's true. That means the
Element is in the array else. It's false. Now. We have the values
This is going to return all the valleys of the set pretty straightforward. Just return the collection
Now I've add we're gonna add an element to this set
But first we have to check if the Elm is in the set already
so we're gonna call the the method we've already defined that has method and
See if the collection has the element if it does not have the element then we can add it
We're gonna push that element to that
Collection array and we're gonna return true else
We're gonna return false. So if we don't push an element to the collection, we're returning false
Now we have removed. This is going to remove an element. So first we just check if the element is in
the collection and if it is in the collection
We're gonna find out what the index of the element is and then we're gonna remove it splice is means we're gonna take out
We're gonna take out an element in the array starting at the index of the element and going for one element
we're gonna take out one element and then we're gonna return true or
We're gonna return false if that element is not in the collection
Then we're just going to return the size of the collection
We're just going to turn collection that length every method we've gone through so far is in the es6
implementation of the set so the es6 set has
values add
Remove in size except remove is delete in the ex6
Set instead of calling remove you're gonna call delete, but all the other things are included
another thing is size is not a method in the es6 set size is a
Property that just means that when you're calling it
You're not going to put parenthesis at after the the method
Because it's just a property so you can do set that size and sort of set that size with parentheses after it. Okay?
now we're going to get into the methods that are not in the es6 implementation of the set, but are
Often included in sets the next few methods actually just help you work with
Sets and when you're working with two different sets
So we have Union this method is going to return the union of two sets
So it's gonna combine the sets but leave out any duplicates in the combination of the sets
so we're gonna
Call the Union method on the original set or I'm gonna pass in the other set that we want to combine
We're gonna create a new set
which this should be my set same what's down here because we want to make it distinct from
The es6 set so we have the the Union set which is just a new set
That's what we're going to combine the sets into we have the first step
Which is this stop values and the values were just calling the the values?
that up here to return the collection and
The second set is going to be the other set that values
For a new first set for each and for each value in that set
We're gonna do a union set that add to add the value then we do the same thing second set for
Each and for each value in the second set we're going to add the value
Remember the add method already does not add the value if it's a duplicate
So the Union set now will not contain any duplicates and since for the set data structure the order doesn't matter
We don't have to have the values in any particular order and then we're going to return the Union set
Now we have intersection which is going to return the intersection of the two sets as a new set
So we're gonna make a new set here intersection set equals new
My set the first set again
We're gonna call the best values to get all the values in the first set now for each value in the first set
We are going to check if the other set has the value
We are going to add it and then we're going to return the intersection set
So the intersection is just all the items that are in both sets
And that's we're gonna return that as a new set and this next function
We're also gonna have to add them my there. So this is the difference
So the difference between the sets so all the items that are in one set, but not the other set
So we're gonna create a new set again the different set. And again, we're gonna get the values of the first step now
This is very similar to the intersection. We're going to go through each value in the first set and
If the other set does not have the value remember up here we were seeing its other set hand the value now
we're gonna use the not operator the exclamation point to see if
The value is not in the set and we're going to add that to the different set then we'll return
the different set and the last method we're going to talk about is the subset and
This is going to test if the set is a subset of a different set. So it's going to test the first set is
Completely contained within the second set. So it's just gonna return true or false
so we're gonna pass in the other set we're gonna again get all the values of the first set and
we're going to call this function first set that every and what that
Every method is going to do is going to test whether all the elements in the array
Pass the tests implemented by the provided function. So we're gonna test if all the elements in the first set
Will pass this function which is other set that has value are all the elements in the first set
Are they in the second set? So we're gonna see if the first set is a subset of the second set
So that's the set data structure and let's quickly just show you some some uses of the set
So we have set a as my new my set set B is new my set
We're going to add to set a a look edit set B B
we had to set BC or ad to set B a and we're going to add to set B D and
now we're gonna see if set a is a subset of set B so is
Set a is every item in set a which is actually just the letter a and set B
Which it is because it's right here. Let's run that and it should say true. Let's do some other things
Okay, and this is the set a that intersection set B is going to return a new set
which we are then going to call the values function so we can see all the valleys in that set and
it's just a
because the only value that's in both set a and set B is a
But we can do a lot of the same things with the built in set I'm gonna copy all this instead of long
That's my set or just going to be half set. We're gonna do set C and set D
Okay, so here's one difference with the es6 set
Is that when you call the values method instead of returning an array, it's going to return an iterator
So you can see objects set iterator here and then you can still iterate through all the items in the array
besides that all the other
Methods that a set has are very similar to the methis ette that we implemented so we can do set
D delete
Now this is instead of remove
So we're gonna delete the a and then we're going to cancel that log and check if that D has a
And we can see it's false because it's been deleted
And
We can also try to add
D which is already in the set
Oh and there is one final thing that's different with the es6 implementation
The add method is not gonna return true or false
Whether the item has been added or not besides adding the item what it's going to return
So whatever it was, it's gonna cancel that log is is the set itself. It's not an array of the set
It's going to return the full set. So if we run that you can see here
It's going to return the set which is an object
And since it's an object, it's not gonna show all the different items in this set. Okay, that's the set data structure
The queue data structure is a way to hold data
it's similar to a stack while a stack is first in last out a queue is first in first out an
Example in real life is when you were waiting in line to buy something in a store
The first person to get in the line is the first person to get to the cash register
Another example is a print queue when a lot of people are printing documents at the same printer
The documents are printed in the order. They were sent to the print queue in
JavaScript just like a stack you can implement a queue with just an array
If you want a limit and array to just the traditional queue methods, you must create it yourself
Let me show you one such implementation
so we have the queue right here, and we're going to have a
collection that's going to collect all the items in the queue and this is just kind of a helper function to
Print or it's a console that log the collection and here that the main main methods of a queue we have in queue
which is going to push the
First item onto the queue and then we have DQ which is going to take an item off the queue
so there's two ways to do it with an array items can go into the array at the beginning of the array or
Items can go in the array at the end of the array in this implementation
items are going into the array at the end of the array and
Then they come off of the array at the beginning of the array to put an item onto the queue
We're just going to push that I know that element onto the queue then to DQ. We're going to use
The rage IFFT dot shift just pulls off the first item of the array
It removes the first item of the array and returns it another cue method is front
This is just going to return what item is at the front of the array without
Removing the item off of the array so we're just gonna do collection output
just going to return what items at the at the zero index of the collection array and
Size we just try to figure out the size of the queue pretty straightforward just collection that length and then is empty
Check if it's empty if there's not no items on the queue. So, let's see how that was gonna work here
I'm just gonna uncomment that and run the code
So we in cute we created a new Q then we Inc we in cute ABC
So the line the end of the line is the end of the array the beginning of the line is the beginning of the array
so it's gonna print a B C here and then D Q means that the
item at the beginning of the array is gonna to be
removed so the a is going to be removed and then we're gonna do cute out front which I forgot to put that
console.log here
Okay, run that again
you'll see that it's going to
Check what what elements at the front of the array which is B and I'm gonna print the array again
it's just me B and C because we DQ'd a another way to create a queue is a
priority queue in a priority queue not only do you pass the element into the queue you also pass the
Priority of the element so if all the priorities are the same number
It's going to behave just like a normal queue
but when you pass in elements at different priorities
The elements that are passed in with a higher priority are sent to the beginning of the queue. So all elements with priority 5 are
Ahead of elements with priority 4 but if elements have the same priority, it just behaves like a normal Q
So let me explain how the priority queue works first
Let me show you an example of this code down here where we're using the priority queue
so to create the priority queue and then we're going to in queue something and
so we're gonna pass in an array the first
Element in the array is the item. We want to put on to the priority queue
The second thing in the array is the priority so you can see I'm not pushing them on in the same order two
three one
but if I run this when we that print the collection it's going to print in the order of the
Priority and just to show another example
Let me add an item with the same priority as an item. We already have
And if I run that
You can see these two items have the same priority
So they're in the queue in the order that they were pushed on to the queue
So everything's the same on a priority queue except the in queue function
So in the in queue function first, we're going to check if the queue is empty if it's empty
You're just going to push on the element
But if it's not empty
you're gonna have to check the priorities to see where to put the element on so we're gonna create a variable just to
Check whether we've added the item to the queue or not
And it would fall it starts at false
And now we're gonna have to run through each element in the the collection or the queue to check what the priorities are
So we have this floor loop that's gonna run through each item in the collection and we're gonna check is the element at index one
remember the element that we pass into the queue is an array index zero is the item you want to put into the queue and
Index one is the priority. So is the priority of the element we're passing into the queue
less than the priority of
The item in the collection that we're checking and see we're using this eye from the for loop
We're gonna go through and check every item in the collection
And we're going to check the index 1 which is the priority of that item
And then if the priority is less than the item we're going to add
That item or the element to the collection array
That's what this splice is doing and then we're gonna say add it equals true. We're gonna break out of the loop here and
Then we're gonna be done except if the element hasn't been added
We are going to then push the element to the array and the only thing that's slightly different
Is this DQ method? And this is the way I did is kind of optional you could return the entire
element with the item and the priority or you can do an idea where I just
returned the
Item without the priority here. That's just index 0 of this value
Which is the the items that we got off the beginning of the array. Well, those are cues and priority queues
A tree data structure is a way to hold data that when visualized looks like a tree you would see in nature now
This is actually what we visualized a tree data structure to look like all data points in the tree are called nodes
The top of the tree is called the root node and from here
It branches out into additional nodes each of which may have more child nodes and so on
Nodes with branches leading to other nodes are referred to as the parent of the node of the branches that leads to the child
Leaf nodes are nodes at the end of the tree that have no children also
Any children of a node are parents of their own sub tree in this video
We will be covering a specific type of tree called a binary search tree
While the tree data structure can have any number of branches at a single node for instance C the C here?
There's F G H. It has three branches at a single node a binary tree. However can only have two branches for every node
So look down here. Here's a binary tree each node. Only has two branches
Also binary search trees are ordered each subtree is less than or equal to the painter node and each
Right subtree is greater than or equal to the parent node
Because they use the principle of binary search on average operations are able to skip about half of the tree so that each lookup
Insertion or deletion takes time proportional to the logarithm of the number of items stored in the tree
This is much better than the linear time required to find items by key in an unsorted array but slower than the corresponding
Operations on a hash table. So let's see how this works in JavaScript here
We're going to use classes to create the binary search tree
basically
We're going to create two classes the no class in the BST or binary search tree class
The no class represents each node in the tree and there's any three data properties
We have the data which is what we're actually trying to store and we have this that left and this that right
Which are going to point to the left node and the right node?
So in the binary search tree, we're going to have the constructor which just creates the the root node
Which is the top of the tree which it starts as null and then we're gonna have the add function
So this is how we are going to add something to the tree. So we're gonna add the data
We're going to get a reference to the root node. But if this is the first node node will be null in that case
We're just gonna set the root node to the new note the new data
We just put in so new node data
So we're just gonna create a node based on that data
If it's not the first node
We're gonna have to figure out where to put this node in the tree to figure out where to place the new node
we are going to use a
Recursive function so I'm gonna create this function, which is search tree
We're gonna pass in the node which starts off as a root node
If the data we pass in is less than no dot data
That means we're going to put the note on the left side of the tree
so if
The node dot left side of the tree is null we're just going to assign node dot left to the new node
And then we'll return but if no doubt left is not null. We're going to return search tree
No doubt left that just means we're gonna continue
Searching this is where it the recursive nature comes in
It's going to run the search tree function again and continue working down the tree to find where to put the node
And you can see here else if if the data is more than no data
That means we're gonna put the note on the right side
So if no dot write equals equals equals null then we just assign no dot right to the new node
And we can return else if if the node right does not equal null. We're gonna have to keep searching
So we're gonna return search tree. No dot right so else that means data is not less than no dot data data is not
More than no dot data, so they must be equal if they're equal. We're not going to add the data to the tree
We're just gonna return null. So this is the search tree function
And this is how we initially call the search tree function return search tree node, which starts out as a root node
But then it can be called with different nodes as it's going recursively through the tree
Let's say you have 50 in your tree and you have 17 in your and you want to add 23 first
It's going to see that the note is not null because you have things in your tree and then it's going to run the search
Tree function putting in the root node, which is 50, then we'll see if data is less than no dot data
Which it is because 23 is less than 50. We're gonna go to the the node dot left if no doubt left is
Null we would put it here, but it's not because there's a 17 here. Remember we're just adding the number 23
So else if if left no doubt left does not equal null, which is true
We are going to return the search tree. No dot left
So we we are now gonna run this search tree function but passed in the 17
So now we're gonna see does is data less than no data
Well now date is 23 but no data is 17. So this is false now
We're gonna go down to this is data more than node data. Yeah 23 is more than 17
Well is no dot writeln all in this example?
we're saying that 23 isn't there so no dot right would be null and
Then we can just set no dot right to be the new node the next functions
We're going to talk about our find min and fine max
So we're just gonna be find the minimum of the array and finding the maximum of the array if you look at this binary search
Tree right here
You can see the minimum is all the way on the left side 9 the math is all the way on the right side
76 so just using that knowledge makes it easy to find men and find max
So I'm going to set the current node to the root node. And so the minutes can get all the way on the left
so
While this dot Left does not equal null the current node is going to be current dot left and then at the very end
It's gonna return current data. So we're gonna check this if the left side is not null
We're gonna go to the next one
If it's not learn all we're gonna go to this one if it's not null when we go to this one now
The next is null because there's nothing to the left of 9, so we're gonna return current data
We're gonna return the 9 cuz that's the data on the very left side fine
Max is just the same way but the opposite we're gonna start at current which is going to this dot root
Which is gonna start at the top while current dot right does not equal null
Well, this does not equal null fit at 72
Then we're gonna go to the next loop current equals current dot right when we go to the next one
But now current that right isn't all because there's nothing to the right of 76 so we can just return
Current data now we have the find function now is present is very similar
But instead of returning the node, we're just gonna return true or false whether the data is in the tree
So we're starting at the top
They're written out while current that means while there is a current node while current is not null
We're going to do the following if data equals equals equals current that data return true
That means we found it if we haven't found it we're going to see is data
Less than current at data now current equals current out left. So we're gonna start searching on the left side else
Well data must be more than current data
So we're going to start searching on the right side
and we're going to keep searching and if we never find it if
We never find that data equals equals current that data and return true
That means is not in the tree and we can return false
Okay, the remove function is a little more complicated than the other functions
We've covered just like in the add function and their move function. There's gonna be a recursive function
So we're gonna create this function here kant's remove node equals function
Where we're gonna pass in the node and we're gonna pass in the data
which is the data what we're trying to remove so we have this whole function here and
Then here's where we're gonna call the function at the end
This that root equals remove node and we're gonna pass in this that root and data
We're assigning this that root to whatever is returned to this function here
We're gonna pass in the root node, because you always start with the root node, and then the data that we're searching for
So, let's see how that works
first of all
We have to check if we have an empty tree if the node equals null then we have an empty tree and we can return
Null now we're gonna see if does data equal no data
So we're trying to see if we can find that data in the tree
So if we've found the node with the data, this is what we're gonna do
There's actually three different options either. No one has no children. That would be just like the 76 if there's no children
We just completely delete that node
So if no doubt left equals null and no doubt
Right equals null then
He's there's no children just returned know when we're returning null were setting the node that had that data
to null now
We're gonna check if the node just has one child if node has no left child. If no dot left equals null
That'll be just like this 54 here
There's a node on the right but there's no node on the Left if node outlet left equals null then
We're just gonna return no dot right?
That means we're gonna replace this node with whatever is on the right, which is 67
So instead of 72 points in 54 that will be replaced with 54 ZnO dot right?
Which is 67 and if there's no note on the right, we're gonna do the same thing
We're gonna just return the node that's on the left to be the the new node that's being pointed to it gets more complicated
When the node has two children like such as v 17 if you want to replace node 17
you can't just
Put in 12 here because then what will happen to 23 is you can't just put in 23 here
It isn't what will happen to 12. So let's look down here. This picture down here is kind of small
Let's say we're trying to remove this 3 here that has the red X in here
The way to remove this node right here would be to replace it with this node down here
so if we remove 3 we can place we can replace it with 4 and then
Everything will be right with the binary search tree. So if you look at what it would become
Over here. We just replaced a 4 down here with the 3 up there
But how are we gonna get down to that 4 well first we have to go to the right sub node
And then we have to go all the way down to the most left sub node after we've gone to the right sub node
So, let's see that we're gonna create in node, which is going to be no dot, right?
So in this case the temp if we're trying to delete the 3 the temp node would be no debt
Right, which would be the 6 here? Well, no tip node. That left does not equal null tip node equals
No dot left. That means we're gonna keep first. We're gonna go to the right of the node
We're gonna delete and then we're gonna keep me gonna keep going to the left until we get to the last one on the left
Side and this one just happens before there's no more to go down because you just have to go down one
But if there was more to go down to it, just keep hopping down until it got to the most left node
Now we're gonna set no dot data to tip. No data. So the node is the three up here
So instead of the data of this node, being three the data the note is now four because Tim no data is four now
I'm gonna set node dot right to equal and now here we're gonna call the remove node function again
this is where it starts becoming recursive and we're gonna pass in the Noda the node on the right and
the tip node data, and this will keep running through the function and
Set up the right side of the tree
Correctly we see here we were saying if data equals no data
Else if data is less than no dot data
that just means we have to go to the left side of the tree because it's less and
Here we're gonna call we're gonna say that no doubt left equals remove node
and we're gonna call this recursive function again and pass a node up left and the data and
Then we're gonna return the node else
That means data is more than no data when you know dot right and then call this recursive function again
And no dot right data, and we're gonna return the num the node
So you can see that the leaf is the most complicated one that we've covered especially when one node has two Leafs
So let's look at how you use a binary search tree. At least this one that I've created so far
So let's open up the console here. I'm gonna do Const BST equals new BST. I've created my binary search tree
we're gonna add four at two six one three five seven and
then I'm gonna remove four and then we're going to file we're gonna console that log the min and the max
Two times and I'm gonna check to see if 4 is present. Another thing we're gonna do is we're I'm gonna add in you remove
Seven and we'll run that again. You can see it first. It's the minimum is one
It's gonna console that log max which is seven
but then we remove seven and now the max is going to be six and
We're gonna see is this present is for present false note 4 is not present because we've removed in
This video covered all the key methods common to a binary search tree
however in a future video I'll be going over a few other things you such as finding the tree height and
Traversing the tree through in order preorder and postorder traversal if you want to play around with this code
You can check the link to the code in the description
Finding the tree height and tree traversal
Height in a tree represents the distance from the root node to any given leaf node
So if you look at this example over here the root node is nine
That's height zero, but if you see four and seventeen here, that's height one
three six and twenty two
Height two five seven and twenty our height three, so it's the distance from the root node to the leaf nodes
They're kind of like layers of a cake. And that's how you're gonna count them
Different paths in a highly branched tree structure may have different heights
but for a given tree
There will be a minimum height and a maximum height and if the tree is balanced these values will differ at most by one
So before I show you the code to implement those things I'm going to show you the use of the code
We're going to go all the way down to the bottom
Where we create a new binary search tree and then we add all these values with the those values
They are the same values as in the picture over here. We're going to find the men height
We're going to find the map site and we're gonna check if it's balanced
Let's just comment out these now. So it's only the men height is one in a console the mattes
That is three, and it's not balanced
The men height is the distance from the root node to the first leaf node
without two children
So if you look on here
17 is a root node, without two children. It has a right child, but doesn't have a left child
So the minimum height you started at the root node
Which is zero and then you count to the next level which is one. So the min height is one
Now the max height is just the distance from the root node
To whatever the the most bottom node is so five seven and twenty are all at the max height. So zero one
two
Three. So the Mac side is three now this tree is not balanced because remember if a tree is balanced the values between the
Min height and the max height will be at different most by one you can see that there's a missing
Number here. The reason why this tree is not balanced is because there's no number here to the left of 17
But if I uncomment out this code here
We're gonna add ten now ten you see when it's being added
It's going to add to the left of seventeen because it's more than nine, but it's less than seventeen
so the tin will fill this spot right here and
Then we're gonna find the min height the max site and then check if it's balanced again
Okay. So now the min height is two and the max height is three the min height is going to be either this three or
The ten that we just add that it's not showing up in the picture, but just imagine there's a 10 right here
So we have 0 1
And then the min height is this level right here
Because this is the first level that there are node without two children if you imagine there's a 10 right here
so that's 2 and then 3 is out here right now is
Balanced is true the difference between the min height and max height is at most 1
So it's going to have to be either 0 or 1
To be balanced when a tree is balanced then searching through it is much more efficient
We're not going to cover this in this video
But there are ways that you can make a tree
Automatically balance itself when you add new items and when you delete items this creates greater
Efficiency when searching the tree. Okay. Now we're going to look at these last lines. I have to have commented out here
these are ways to
traverse the tree tree traversal methods can be used to explore tree data structures and basically find all the values in the tree in
Depth-first search a given sub trees explored as deeply as possible before the search continues on another sub tree
When I show you an example it will that will make more sense, but there's basically three ways that this can be done
There's in order traversal
Preorder traversal post order traversal and this last one. I'm going to talk about later this level order traversal
So let me run this and then I'm going to explain it
So here you look at the bottom of the console and you can see what we've logged here
For in order traversal, you're going to begin the search at the left most node and in the the rightmost node
So you can see this. This just has all the numbers in order 3 4 5 6 7 9 10 17 20 22
So there's all these numbers in order you're gonna begin at the left notes most note and you're gonna add all the numbers in order
now
preorder traversal
You can explore the root nodes before the leaves. So let's look at this
I'm gonna read off these numbers down here and I'm going to show up on the picture where they are in the picture
So we're looking at the root nodes first in the list 9 is first that's a root node
Then 4 that's a root node, then 3 and the next newt is gonna be six and then five and then seven then
17 and then 10 which we don't have on this picture then 22 than 20
This is a pre-order focuses on the root nodes first and then adds that their notes below that the postorder
Explores the leaf nodes before the roots. So look at this one
the first node on the list is 3 because it's a leaf all the way down and then we have 5
Because that's a leaf node, and then we have 7 and then we're gonna go to 6
We're not gonna hop over to 20 over here because that's not a completely different branch of the tree
You have to finish all the leaf nodes on one branch before you go to the next branch
So after 6 is 4 now is where we jump over the leaf nodes on the next branch and we use 10
Which again is not on the picture then 20 then 22 then 17 and 9 this level order is called a breadth-first
Search this explores all the nodes in a given level within a tree before continuing on to the next level further
it's going to do level 0 which is 9 if you see these numbers on here, and the next line is
Next is gonna show 4 and 17
Then 3 6 22 then 5 7 20. So let's go over the code
So first, we're gonna go over the code for them main height and the find max ID and then it is balanced
So that is balanced is pretty simple because you just call these functions that I haven't talked about yet
But you na'kal find min height and see if that's less than or equal to
find max height minus 1 so this is going since this is a a
Conditional statement is going to return true or false
So as an example
if you remember before we added the ten we have the min height of one and the Mac side of three if
This Mac side is 3 3 minus 1 is 2 so is 1 less than or equal to 2
no false, so we know that the tree is not balanced we have false right here, but then we run it again down here and
the max height is
3 and the min height is 2 if we do 3 minus 1 that's going to be 2 so now we have is 2
Less than or equal to 2
Yes, so we're gonna return true. So that's how we're gonna find out if it's balanced now, let's look at fine min height
This is going to be a recursive function you can pass in a node, but if you don't pass in a node
It's going to set the node to the root node here
and then it's going to check if the node is null and
Return negative 1 if you haven't added anything to the binary search tree, it's gonna return negative 1 for the height
We're gonna set the left and right to calling the Fineman high on the left and Fineman height node
Right. So this is where the function becomes recursive
Eventually, one of these two is going to be negative one because the left or right node is going to be null
So here we are going to add one to the left if left is less than right
And we're going to add one to the right else
So if right is less than left and 4/5 find max Heights, it's it's the opposite
So instead of having the less than here, we have the more than here
So here we're going to return left plus one as if left is more than right else
Returned right plus one. Feel free to check the code in the description to play around with this yourself
The inorder preorder and postorder there's a lot of similarities to the code. So let's look at the inorder traversal first
The only thing that's going to be different and each of these
in order preorder and postorder
Are these three lines and the only thing that's going to be different in those three lines is the order of the lines
So for all of them
we're going to check if the root is null and
In all this just to check if there's even a binary search tree that exists or if there's any values in it
So if we find out that there is a binary search tree. We're going to do these things
we're going to create a new array of the result and we're going to add each value in the
in the tree onto the result
So we're going to create this function traverse in order function and you can see down here
We're going to call that function and pass in the root node
And then after the function has been run you're going to return the result
So inside this function it's going to be recursive
And remember these three lines are the only thing different between inorder preorder and postorder
It's going to change the order that we check things
So in order we are going to first do this line. So this right here is
short-circuit evaluation
whenever JavaScript evaluates the and
Operator like this if the first thing is true
It will also run the second command if the first thing is not true
It will not run the second command
Check my video on short-circuit evaluation to find out more about that. So if no dot left is true
that means if no doubt left exists, then we are going to
Run the trench reverse in order
Function on no dot left and that just calls the same function again and passes n note that left then we're going to push
No dot data. So we're going to push the value in that node
Onto the result array and then we are going to check if no dot right exists
If it does we are going to call the traverse in order function on no dot right and if we look down here
Like we're I said, they're just these three lines are different. So in pre-order, it's going to push first and
Then it's gonna call the function on note left and then it's gonna call the function I know dot right in
Post order it's going to call the function on no dot left
Then I call the function on node dot right and then push the data
so just to order that we call these commands is going to change the order of
How we get the result when traversing the tree again?
You can check that code and play around with it until you can figure out exactly how it works
I'm going to go down to the level order function in this method
We start by adding the root node to a queue then
we begin a loop where we
DQ the first item in the queue add it to a new array and then inspect both it's child sub trees if
It's children are not null they are each in queued this process continues until the queue is empty
We are treating a result array that we are eventually going to return now. Here's just that the queue array
this is just a
Temporary array that we're using that we're eventually going to put things off that ray onto our result
If this that root is not null if there actually is a binary search tree
We're going to push the root node on to queue and this is a while loop
So it's gonna continue going through this until we've actually added all the all the elements from the tree
So while Q is the queue length is more than 0 we're gonna keep doing these things
so first we're going to let node equals Q dot shift now shift just takes off the first element in the array and
Returns that element so we're gonna put the root node into node because it started out as the root node
And now Q is not going to have that root node on it anymore
And we're going to push no data onto that result
so we've just pushed 9 onto the result and if you remember
9 is the first thing in the the level order result now if no debt left does not equal null
We are going to push no left onto the queue and if no dot right is not equal
Now we're gonna push note that right onto the the queue and then then we're going to go back through the while loop
We're gonna take off the first node and put into node, which remember is going to be no doubt left
So we pushed on here and we are going to push that value to the results
We're going to push forward to the result
And now we're going to push no doubt left and we're gonna push no dot, right?
So in the queue, we're not gonna have 3 and 6
but when we go back through the while loop and we
Shift off an element even though we added three and six in the last iteration of the loop
The know that we're shifting off is going to be 17
Because shift is going to take the first item of the array off and three and six are at the end of the array
so then it's going to get that value and so on it's going to keep going through this until it's got every
value from the tree
a
Hash-table is used to implement associative arrays or mappings of key value pairs
Hash tables are a common way to implement the map data structure or objects
They are widely used because of how efficient they are
The average time for each lookup is not tied to the number of elements stored in the table
in fact
The average time complexity of hash tables and big notation is o of 1 for a search insert and delete
That's very fast
The way a hash table works is that it takes a key input and then runs it through a hash function a hash function
Basically just Maps strings to numbers and usually the numbers just correspond to indexes in an array
so for example
Here are the strings we pass through the hash function and then we get the numbers over here a hash function needs to be
consistent so when you run a key through the hash function
It always gives the same number and it should map different words to different numbers
If two words get hashed to the same number
This is called a collision you can see in this example John Smith gets hashed to two
Lisa Smith gets hashed to what was ero 1
Sam go for and then Sandra Dee also gets hashed to 2
So this is a collision because both of these names once they run through the hash function
Get turned into the same number or the same index for the array
One way to handle collisions is just to store both key value pairs at that index
then upon lookup of either you would have to iterate through the bucket of items to find the key you are looking for this could
Take a little extra time because of the iteration
so here's another example where it's showing that the names are going through the hash function and then it's showing basically the
Information that's being stored in the bucket
So this would be the array index and then in that array index or the bucket, we would store the phone number
So this would be like a phone book the numerical value from the hash function is then you as the index to store that
Information then if you try to access the same key again
The hashing function will process the key and return the same numerical result
Which will then be used to look up the associate value which just means that once you store all these things in the array
Once you want to get the number again
You would just pass in the key John Smith into the hash function
It would give you the exact same array index, too
And then you would get the information returned to you, which is the phone number now
You will probably never have to implement hash tables yourself because most languages
Including Java Script already have them built-in in JavaScript. Hash tables are usually used to implement objects
However, it can be helpful to see how they are implemented just to gain a better understanding
So I'm going to show you the code for a hash table so you can see how they work
First of all, we have our hash function
Where we're gonna pass in the string that we want to hash and then the Max
Max is the number of buckets that we're using in our hash table to store values
we're gonna start with hash being zero and
We are going to for each character in the string string that link for as long as the string is
We are going to add the care code of each character
Each string character has a numerical value associated with it
so basically
We're just adding up the character codes for each character in the string and putting into the hash
Now instead of returning the hash we're gonna return hash modulus max
That just means we are going to divide by the number of buckets and then return the remainder
So if we had 5 buckets if we're divided by 5
The remainder is either going to be 0 1 2 3 or 4 and then that would be the index that we're going to place
The item into the array now
This is a very simple hash function just for an example, but they can get much more complicated now
Let's go into the hash table function
so in the hash table function, we're gonna have our storage array which is where we're going to store all the
data, we're putting into it and
The storage limit now, this is the number of buckets in the array at first
I'm just gonna show you with just four different buckets
But normally actually this number will be much higher and this is just a utility function just for this example
So I can easily
Print all the items in this storage array I can easily log them
So here's where the real methods come in for the hash table if we want to add some information
So first you're gonna pass in a key and a value
We're gonna figure out the index of the array by running it through the hash function
so we create this hash function where we're gonna pass in the key and the storage limit the number of
buckets that we're gonna have in our hash table and that's going to return an
Index that we went over before if there's nothing in that index in the storage array if it's undefined
We're just going to set that index to be this key value pair array
Else if it's not undefined that means there's already something in that bucket
So first, we're gonna set insert it to false and then we're gonna go through each
index to see if the key already exists if the key already exists, we're gonna set the new value here and
Set insert true if the key does not exist, then insert is still gonna be equal to false
So we're going to push in the new item. That's where we'll get multiple
Entries into one bucket. So the next thing is if we're going to remove an item from the hash table
So if we're gonna remove you're just passing the key of what you want to remove and now we're gonna look up the index by
passing it into the hash function if the index that length equals one, that means there's only gonna be one item in that bucket and
the item in that bucket
Equals the key that you passed in then you can just delete that index. You can just sleep that item
But if it does not equal one
that means there's probably a few different items at that index and we want to only
Delete the item associated with that key. So we're going to go through each item in that bucket or in the index and
If the key equals the key we passed in then we can delete that item
The zero index is the key. The one index is the value
So let's go how we would look up an item again
we're gonna set the index using our hash function with the key that we passed in and the storage limit if the index there is
Undefined we just return undefined. It's not the item is not in the hash table else
We're going to go through each element in that bucket
If the element equals the key then we can return that element. So let's look up a few examples first
I'm going to show you an example of the hash function
Here if we run that to me three and every time I run that you'll see in the console three three three
Every time I put Bo it's gonna put three, but if I put a different name here and I run that
You can see on the console. It's gonna be five and now every time I run two has to be five
so with this hash function
It's going to always be a number between zero and nine because we're passing in ten as the number of buckets
So now let's actually see the hash table
So here we're gonna create a new hash table called hte for hash table
We're gonna add Bo who's a person add find out who's a dog retsu the dinosaur tux who's a penguin?
Then we're gonna look up tux and then we're just gonna print the entire thing. So, let's see what happens in the console
So we saw that tux is a penguin now, let me bring this over a little bit
It's going to show our entire hash table now
Normally, you're never gonna print out the hash table like I did to the console
But I just did that just for learning purposes if you remember up here
We have the storage limit set at four so we only have four buckets
the reason why I had it set at four is so we will see what it looks like when there's a
Collision when there's two things in one bucket just by coincidence
The first buck is undefined that means none of these words
Hashed to zero and then if we look at the second bucket, that's right here
There's actually two key value pair in the second bucket
so both bow and tux both gave
One when it went through the hash function and then you can see in this bucket right here
We just have one item and then this bucket right here. We just have one item
So when we pass in reps to the hash function, we got three returned
But if we go up here and we change the number of buckets to something like 14 now
I'm gonna try running that again
If you look right here now, there's a lot more undefined because most of the buckets are now empty
but this bucket only has one item that
Book has one item and then the last two books have one item and there are no collisions now each bucket only has one item
Now this has just been a pretty simple example of a hash table
Implementation but it's enough to give you a basic idea of the hash table
A linked list is a common data structure where elements are stored in a node the node contains two key pieces of information
The element itself and reference to the next node
So in this example the element here will be one and then here's the reference to the next note
This arrows point to the two this two is the element we're storing the information
To and the way this length linking to the next node, like arrays linked lists can be used to implement many other data structures
linked lists have some advantages and
disadvantages when compared to arrays
Traditionally arrays are just have a fixed size and linked lists have dynamic size so you can just keep adding
Links and you don't have to do anything differently
JavaScript kind of hides some of this but when you create an array can only be a fixed size also
arrays have pretty inefficient insertions and deletions while linked lists are very efficient search terms and deletions a
Benefit to arrays are the random access which means you can say you want something at index five and you can instantly get the thing
At index five however with linked lists if you want something at index five
You have to go through every element
in the linked list to get to index five and then for arrays they may result on much memory waste to make up for the
Fact that arrays can only only be made at a fixed size
Sometimes they will be created a lot bigger than what you really need to make sure you have enough room for everything
However in a linked list because of the dynamic size
There is no wasted memory and then we have really fast sequential access for raised and slow for linked lists
So every linked list is gonna have a head so we have this head pointer here that points to the first node
And then it's also going to have a size. So that's just the amount of node
So in this example here the size will be three and you can see each node points the next node in the last node it
Just points to null because there is no next node
So if you look at the code over here
we start with the head of null because we don't have a head yet and the length is going to be zero and
The linked list is made up of nodes
So here's how we're going to create a node we pass in an element and this Telma is set to element this
Next is set to null
So this not element in the picture is the info and this that next in the picture is the link so it starts off
Just like the last element where the link is point to null next is point to null
then we just have a few simple functions this step size just returns the length and
this the head just returns the head and
Here's the add function whatever we're going to pass in to the linked list is going to be the element
So you're gonna add the element and then we're gonna create a new node
With that element. So after you pass in the element and it creates this new node
The element of the node is set to the element you passed in but the next of the node is set to null
So if head equals null that means there are no nodes in the linked list yet
so we just set the head to equal the node and at that point there would just be one node in the linked list and
The head would be pointed that first node else. That means there's more than one element list
We're gonna set the current node to equal the head and let's add a var in front of here
So this just means that we're gonna start at the head node
Which you always have to do whenever you're doing anything to a linked list
You start the beginning and then you to go through each item in the list while current node dot next that means
While there is a current door next while current node that next does not equal null
You can see at the end. Remember the link equals current node next
So at the end it equals null
So before the end of the list the current node next which would be the link does not equal
Null it equals the next node
So this just means while there is a next node current node equals current node next
So that's just a way to hop from node to node on the list. Once there is no current node next
That means we're at the end of the list the end of the list is where we want to add the element that we're adding
Now we'll set current node next to equal the node once we get to the last node in the list
We'll set the Curnow dentin X or this link to equal the new node
We added instead of null and we just increment the length
The remove method takes an element and searches a linked list to find and remove the node containing that element
so you're passing the element that you want to remove and
We always start at the head current node equals head
And then we also need to know the previous node when you're gonna remove something
So if the current node that element equals element if current node element equals element
Well, that just means that the head node is the element
We're trying to remove so if we're trying to remove the head node
We just have to set the head to current node next
So the head pointer will be pointing to the next node if the head node is not the node
We're looking for we go to the else
So else while current node to element is not equal known element basically while the node Ron does not equal the node
We're searching for
Previous node is gonna equal the current node
Like I said, we have to keep track to the previous node
And then the current node is going to equal current node next
It just means we're gonna keep going through this while loop and keep jumping to the next
Node on the list until we find the node we're looking for let's let's say if this second note on this example here
We're minus that previous node that next to equal current node dot next if we're trying to remove this second node
We're gonna step previous node next. So the previous node that next would be the first node
So there'll be the link the link is now going to not point to
the current node the link is going to point to the current node dot next we would skip over that node and
point to the current node that next right here and that's how a node would be deleted from the linked list and then we just
decrement the link
now here's another quick function is empty return length equals equals equals 0, so if filling T equals zero
We're going to return true if it doesn't equal zero
We're gonna return false and you may want to know the index of a specific element
So we're just gonna have to hop from node to node until we find that element and then return
index so the current node is gonna equal head start at the beginning and next is gonna start at negative one and
So Wow current?
No, that means while there is a current node while it's not null. We're gonna increment the index
So at this point we start the beginning we've incremented the index. So where the index is now is zero
So if current node that element equals element returned index
So if the first element which would be this info equals what we passed in up here, we're gonna return the index
So if instead of the head node
we're gonna return the index zero if not
current node equals current node next and then when we continue doing this while loop and just hop from node to node and then then
We're gonna eventually be able to return the index as we keep adding
one to the index for every time we do the while loop and if we go through all the whole while loop and don't find
Anything we're gonna return negative one that just means the element is not in the linked list
So we just found the index of an element now going to find the element at an index. That's just the opposite
You're passing an index number and you're going to return the element
So we have current node equals head
Count equals zero and here's the wall loop here while count is less than index. That means we haven't gotten to the index
We're searching for increment count and current node equals current note that next so that means we hop to the next node
so we're gonna keep going through every node in the list until
Count is not less than index. That means count equals index
So we've reached the right index so we can just return current node that element
Yep, you're gonna pass in the index and elements and add
Remember, we you always add to the end of the linked list
But an add at you can add in the middle of the list
So just like a ID we're gonna create a new node with the element
We pass them and the current node is gonna equal head. We always start at the beginning
We need to keep track to the previous node, and the current index is gonna equal zero
So if index is more than length that means we've passing an index that's way bigger than the actual length of the linked list
so we cannot add at the index when we return false if
Index equals zero that means we're trying to add the element to the head node. So we'll set node n or no
It is a note that we just passed in so the next element is now gonna be the current node
Which would be the current head node?
And then we just set the head to equal the node that we passed in else
We don't want the index to be the head node while current index is less than index
We're gonna go through each index until we find the correct index so cray index increment
We're gonna set the previous node to equal the current node. So we want to keep track of the previous node
The current node is gonna equal current node. Next we're gonna keep going through this while loop until we find the correct node
so if we want to add a node as
Index one or the second node on the list once we get to that index
We're gonna set node X equal to current node
So or no debt next is the node we passed in and we're gonna set that to equal the current node
Which would be this index right here?
then we have to set previous node that next to equals and note that we're passing in and then we just increment the length and
the last function I'm gonna talk about is remove it now remove it and a net are
Very similar a lot of the lines are the same except we're not gonna create a new node
The kernel is gonna be the head. We need a previous node
the current index is gonna be zero here is a slightly different thing if the index is less than zero or
If the index is more than or equal at length return null
so we cannot remove a negative index and we cannot remove an
Index greater than the length of the list if index equals zero, we're trying to remove the head node
So we just set the head node to equal the current node next
So instead of the head pointer point to this node right here that head pointer is going to point to the next node right here
else this part is just like the ad and we're just going to keep going through each element on the list and once we find
The element we want to remove like let's say we're removing this second element at index one
We're going to set previous node next to equal current node. Next. We're going to set the previous node
next or this link is going to point to whatever was in the link to the current node, or
So this link is going to point to now
this note right here and we're gonna completely take out this one and then we're gonna do length - - and
Return the note that we're removing and now we're just going to quickly show an example of using the linked list
We're going to call the linked list
Conga because a linked list is kind of like a conga line and let me bring up the console
So we're gonna create this new linked list. We're gonna add some items kitten puppy dog catfish. We're gonna show the size
We're gonna remove the third item on the list. So we'll run them and see we're gonna remove cat now
let's copy this we're gonna do element at
Then we'll try index app and for the element we're gonna put puppy look I mean index of so we remove cat
Now we check the new element three, which is gonna be fish and the index of puppy is gonna be one
Kitchen would be zero copy is one and the size is four. Well, that's the linked list
a try
That's how this is pronounced right here
A try sometimes called a prefix tree is a special type of tree used to store
Associative data structures a try stores data in steps each step is a node in the try
this is often used to store words since there are a finit number of letters that can be put together to make a string a
Possible use case would be to validate that a word is in a dictionary
Each step or node would represent one letter of a word
So if you can see over here, this is an example of a try
This word right here will be B a ll ball the steps begin to branch off when the order of the letters
Diverged from the other words in the try or when a word ends. So if you get the word be a ll
But you also have be a T bat
So the first two letters ba are part of the word ball and part of the word bat and then down here you have doll
do
dork and
Dorm, if you look at the red stars, that just means it's at the end of the word
So the word do you can see it's the end of a word?
Even though there are still letters in other words after the O
So let's look at the information in each node from the code here
Each node is going to have a keys which is just a new map
And this is the es6 map structure. It's kind of like an object
It has just key value pairs
and in the in these keys the key value pairs are kind of like
the name of a folder in a folder in a directory structure
so if you can imagine these all folders in the root node, there is
The keys map that's going to have B D and s and each of the key value pairs are the B
The name of this folder is the key in the map and the value of that key is
The folder be the actual contents of the folder B. And so that D is
Key in the map and the value the key value pair
The value is going to be the actual contents of the folder
Each snows gonna have a list of keys, which is just a list of all the other letters
That are inside that folder or in that inside that note and then we're gonna have an end data
That just means is this the end letter in a word?
so in this picture all of
The node with a star have end
Set to true and all the nodes without a star have end set to false now
We just have a setter function set end and is equal to true is end
So it's just gonna return true or false if it's the end of the word
So now that we've looked at each node in the try
Let's look at how the code to the actual try set up
So we're going to only going to have three functions
We're gonna have add to add a word to a try we're gonna have is word
to see if a word is a word in the try and then
Print this is more of kind of like a helper function just to print all the words that are in the try
So before I go through the code
let me show you how it be used what we're gonna create a new try and
Then we'll get you can add the words like this
And then after you add all these words and these are the same words are in this picture over here
You can check if it is a word is dollar word
Well doll is gonna be word is daughter word
See we have the word do R in the picture
But there's no star on our because door is not a an actual word
even though those letters are in the try and
then Dorf
Well check do R and then there's no F so that's not a word and you can just print the whole thing like that
So if I run that you're gonna see in the console down here
True false false and then you can see the whole list here. So let's go back up to here
first of all, we're gonna create the root node a new node and
Then let's look at the ad function. So this ad function is a recursive function
So when you call it for the first time, you're gonna put the entire word
You want to add to the try and that becomes the input and theer says note equals this dot root
That means if you pass in a note it will use that node
But if you don't pass in a node, it will just use this that root as the default node
So if input that length equals equals zero
That means if we're at the end of the word that we passed in
We're just going to do no dot set end and then return and we're done with the add function
Else if that means if there's more than zero letters that we've passed into this add function
We're not at the end of the word
So first, we're going to check if there's already a node with that letter that we're looking at
so this is if not
No dot keys that has so let's say we're in the root node
no duck keys is a list of all the letters of that root note points to so if it does not
Has if it does not have a letter input zero would just mean the first
character of the string we passed in so if we pass in ball it would this is just saying if
There is not a node with the letter B here
Then we are going to create a node with the letter B
Know that keys that set set is how we're going to create a new key value pair in the keys map
We're going to set it with the key to be the letter
input zero
So input was you don't bracket just means the first letter of the input would pass in
so if we pass in ball the first letter to me B and so remember each key value pair is
Then Nate is kind of like the name of a folder and the contents of the folder
The name of the folder is B the contents of the folder are a new node. So then this is where it becomes recursive
We're gonna call this dot add and we're gonna pass in inputs
abstract one which takes the input and
Takes every letter after the first letter and passes it into the add function again
So if the word was ball
every letter after
The first letter is a ll so we're gonna just pass in the letters all and we're also gonna pass in a node
Before remember twister there with the root node. Now we're gonna pass in this node, which is also the node. We just
Created here. So we're gonna set a node with the letter B
that'll be the input 0 so now we're gonna get the node with the
Input 0 that's the first character. So now we're gonna run the add function but instead of after being at the root node
We're gonna be at the the node B, and then the else is just if there is already a letter by that name
So remember here we added a node with the letter B, but if there already is a letter B like for instance
let's say we already have the word doll and
We're gonna add the word dork if we're at the D and the word doll is already in the Tri and we want to add
dork
Well O is already going to be in the Tri
So if I was already in the Tri we're not going to create the own ode
We're just going to add the the new sub string which in this case would be so our k we're gonna add that to
The nodes that know that keys that get input 0 which would be the O
Node, so we're gonna keep running through that until we've added the word to the Tri and then down here
We're gonna check if the word is in the Tri. So this is where the Tri really performs
You can check if a word is in the dictionary
Much quicker in the Tri than other data structures because we don't have to check through every word
We're just checking one letter at a time. So we're passing in the word
we're setting the node to the root node at first and
Then this is the loop that we're gonna keep running through until we find the word
so
while we're dot linked as more than one while there's more characters to search in the the word that we passed in so if
Not no duckies that has word. This is saying we're gonna check the first character in the word
So let's say we're on the root node
So if there is no key with the first character in the word, like let's say we passed a word tree
Well, there's no T. There's no key with the letter T here so we can return false
We quickly determined that that word three is not in
This try because there's no word that starts with T else that just means there must be a word that starts with that letter
So let's say we're looking for the word it's end
Well, if it does have the letter S then we're going to do these two things
We're gonna set the note remember, which we used to be the root note
But now we're gonna set the node to the the note s because if we're gonna look for the word descend
We're sorting the note to the S note and we're gonna change the word
into the word - the first character
So now we're just gonna be looking for the word end instead of sindh so I'm gonna go back up here now
We're we're gonna keep running through this now. We're on the S note, but we're looking for the word end
And yeah
we'll find the e we'll find the end and we'll find the D and now we go to this very last line if
note that key that has
word
Which would just be a single letter because remember we keep taking the letters off
and so if it has the last letter of the word that we passed in and
It is the end so is end
Then we're gonna return true that word is in the Tri else. We're gonna return false. Yeah
So this last one was just the the print function that's kind of a helper function
And so we're gonna create an array of every word
But right now it's just gonna be empty
Then when a search we're gonna pass in or a search if we don't pass anything here
It's gonna set this is a root node. Actually that we don't even need this
Let me just run that just to see if it does the same thing in the console. Yep
We don't even need to set the note to the root node
Because when we first call the search command down here, we already passed in this dot root
So we're just gonna pass in a node and we're gonna pass in a string
Here if no duck keys. That size does not equal zero
That means they're still still more letters to look through
So for each letters and the keys here, let's say we're on the root node
So the letters in the key would be B D and s so for each of those letters
We're going to run the search command again, and then we're gonna pay Sen note keys that get letter
that means we're going to pass in the the node at that letter so we would pass in the B node and
then we're going to
Add that letter to the string at the beginning the string would be empty
So do string that can concatenate one letter. We're going to add the letter B and basically since this is recursive
It's going to keep going and keep adding each letter
so we keep
Concannon each letter to the string
Until it's formed the whole word and then see if node that is end if we've gone to the last node in the word
It's going to do word dot push string. So that's our word to raid if we've gone to the last letter in the word
we're gonna push the word onto the words array no else that's else to this if statement if the
Note keys that size
Does equal zero then we're at the last letter of a branch if string that length is is more than zero
We're just gonna push that word on to the words array or else
Returned undefined and here's where we call that a search function for the first time
So here's the search function
and then we call for the first time and this is gonna go over and over until it gets every word in the try if
Words that length is more than zero
It's gonna return that where the words the words array or it's gonna return all if there's no words in the array
So that's a try
a
Binary heap is a partially ordered binary tree which satisfies the heap property
It has some similarities to a binary search tree except the order is a little different
Each node has at most two child nodes the heap property indicates a specific relationship between the parent and child nodes
You may have a max-heap in which all parent nodes are equal than or greater to than the child nodes
so you can see the the biggest numbers on top and the smallest numbers are on bottom or
You may have a min heap in which all child nodes are greater than or equal to the parent nodes
So the child nodes are the biggest ones and the parent nodes are the smallest ones
The order between child nodes on the same level does not matter
So you have 10 6 and 12 here here
We have 5 6 & 1
You can see that it goes from a small number to a big number to a small number the order doesn't matter if they're on
the same level
Binary heaps are also complete binary trees
this means that all levels of the tree are fully filled and if the last level is partially filled it is filled from left to
Right. So if you see the example down here, so here's level one
Then we have level two here level three level three is all the way filled
Level four is only partially filled because there's nothing over on the right side here
But you can see it's filled from left to right
Binary heaps may be implemented as tree structures with nodes that contain left and right
References like what? I showed in my binary search tree video
However, heaps are more often implemented as arrays
This is possible because of the partial ordering according to the heap property
We can just compute the parent-child relationship of the elements. Now. This will make a lot more sense with this diagram here
So if you see this array right here, this is the array
Representation of this tree right up here. The number 1 is 20 and that's the root
You can see that right up here and then 2 & 3 are the child knows 19 and 17 right here
And now I want to pull your attention over to these equations up here
so that the left child is going to be I times 2 the right child can be I times 2 plus 1
Let me show you what that means. So if you look at 20 here, which is at index 1 in the array
Also, I should point out that there is no index 0 so when you're representing a heap
You're just gonna leave index 0 as null to make the math work out a little better
so if we go back to
Index 1 well the equation for the left shell is I times 2 so 1 times 2 will be 2
so yeah 19 is the left child and the right child is I times 2 plus 1
So 1 times 2 plus 1 is 3 17. That's the right child. Now. Let's say we go to number 13 here
That's index 4 well if we go to the equation
I times 2 4 times 2 is 8 so if your index 4 and you go to index 8 11, yep
That's the left child now, we start index 4 and we do the right child equation
I times 2 plus 1 that's 9 so if we go to index 9, yep, that's the right child here
So that's how you can use these equations to find the left and right child from an array representation
You can also figure out the parent so the equation for a parent I divided by 2 if we are on
11 that's index 8 8 divided by 2 is 4 index 4 and this really should be floor
I divided by 2 because you divide the index by 2 and then round down to the nearest whole number
For instance 5 divided by 2 is 2 point 5
But if you round out it's 2 and then 2 would be the the index 19 here
Also, you can see in this diagram that the last index is also the size of the heap size 10
This diagram is a max-heap. I'm going to show you the code for a min heap
but in the same file down here, we I also have the code for
The max heap down here so you can check the link in the description
So you can review this actual code yourself and you can review the maxi on your own
But like I said, we're just gonna review the the men heap right now
But before I show you the actual code
I want to show you a visual representation of how it works when you're inserting and
You're removing items from the heap
Those are the main two commands insert and remove and then there's one more I'll show you at the end
But let me show you this
Representation here so you can see this is the array representation
And I'm going to insert some numbers and you'll see them show up as a tree representation. So, let's see 4
You can see 4 goes at the top. That's the the root node. And now I'm going to put in 6
6 just goes down to the bottom there 8
So as it builds the node one thing to keep in mind is that it's gonna build one
Level of the tree at a time
I'm gonna put in 10 that's gonna be on the very left side now so far
I've been putting them in order
but now I'm gonna put in the number 5 here and when I insert the number 5 you're gonna see this it's gonna
First go to the end of the array here. You'll see their array which is gonna first appear right down here and
Then it's going to move up to the correct position
So, let's see that
So then as you see it checks what position to move it up to so I'm going to put in a few other numbers here
See 16 3
Ok, so you see it always puts in at the end of the array or the end of the tree and then it moves it
Up to the correct position now
I'm going to show one more where I put in one where it's gonna put it
put it down here and it's gonna move it all the way up to the top and
It's a check one at a time to see if it has to move it up
also
Another thing would just be removing what when you remove you always just remove the smallest
it's gonna remove what's in index 1 which is always gonna be the smallest and then it's gonna pop the last
Node to the first node, and then it's going to sort them. So, let's see how that works
So did you see that so it moved the last node to the first node?
And then it has to keep checking and keep moving it down until it gets to the right position. So let's move remove 3
Okay, so now let's go to the code and you can see how that works in the code
So before we insert anything
You can see that we've created a heap with an array that just has one item and it's the item null at index zero
So when we insert something we pass in a number and we're gonna push that number on to the end of the heap
So if you pass in the number three, there's going to be index zero is null and next one would be three
now if the length of the heap is
More than two that means there's more than one item in the heap if it's less than two
There's one or zero items in the heap and that makes things really easy. But let's say it's it's more than two
So we're gonna let the index equal heap dot length minus one. So
That means we're finding the last index and the heap while
heap at that at the last index is less than
Heap and then see this equation right here
That is the the parent equation
So now we're saying if the last item in the the array which is the item
We just inserted right here. If the last time of the array is less than its parent
Well if it's less than its parent
We're gonna have to move it up because the smallest numbers have to be at the top in the men heap
So if the index is more than or equal to one that means if we haven't reached the root node
Then we're going to do this now
This is es6 destructuring syntax, which just means we are gonna switch the node
We just inserted with the parent node. We're gonna we're gonna switch them. So here is the parent node
Here is a node. We just inserted and now we're gonna switch them
So the node we just inserted is gonna be first and then the parent node is gonna be next
So it's just a way to swap them for more information about the es6 destructuring
You can check out my video about that topic
so if math math dot floor index divided by two is more than one this just means
If the parent node is not the root node, because remember this is the equation for the parent node
Is the index of the root node
So if the parent node is more than the root node
Then we're gonna set the index to map that floor and X divided by two. That's the parent node
Which if you remember up here we just put the number we passed in
Into the parent node. So now the index is still gonna refer to the number
We just passed in because that number has went into the parent node
And so now we're going to set the index to that node
And since this is a while loop or when I keep going through this and we're going to keep switching the the node
To its parent node, as long as it is
Smaller than the parent node else break. So once it's not smaller than the parent node, we just get out of this while loop and
That's the insert
so let's go down to
Remove it's a little more more code, but it's some similar concepts
So we are always going to remove the top node the smallest node
So we're gonna let this smallest equal heap 1
So that just means that the first node in the array is the smallest node. So that's the easy part
The hard part is rearranging the array after you've removed that node
So if heap that length is more than 2 that just means we have more than one node in in the tree. We're going to
Set the first node in the tree, which remember was the smallest node
But we're gonna set this to the last node
The last node in the array now gets moved to the first node in the array
Now we're gonna heap that splice keep that length minus 1 this just shortens the array by 1
So we just removed the hole the last index of the array completely since we've already moved that to the first
Index if heap that length equals 3, that means there's only two numbers in the the tree and that makes things really easy
Just if one is bigger than the other then we just switch them. This is the destructuring syntax again
So if the first one is bigger than the second one then we switch it
so the second one is bigger than the first one and then we just return the smallest if
There are more than two nodes in the array. That's where it gets slightly more complicated
So we're just going to set the index to equal 1 we're gonna set the left equal two times
I and the right equals two times. I plus one remember that was just that the equations from up above the equations right here
We're just putting him into our formula down here
Now technically you would not need to put this equation here since we know that I equals one
You could just put three here
You just put four here, but this is just so you know, we're using the equations from above
So we're one is the root notes or starting with the runo
So while the root note is more than or equal to its left child
Or the root note is more than or equal to its right child
We're gonna do everything in here. That means we're going to have to
Basically move a down and keep moving it down until we get to the appropriate spot
So if the the left node is more than the right node
Then we're going to switch the root node with the left node
This is the destructuring syntax again, so we're gonna just swap the nodes
So for instance, we would be swapping if we're on this node and this node
We just swap those two nodes and then we're gonna set the index to the left node
So gonna set the index to be the node that was at the top node, but has now been swapped
Else that means the right node is less than the left node. We're gonna switch the node with the right node
So we're just gonna swap with the right node. And then we just set the index to be the right node
So the the node just moved down a little bit and then we set the index to point to the node that we just pushed
Down a little bit and then we have to set the new left and right node
so we would set the left and right no to be the left and right of the the one we just passed down and
then if
The the left child or the right child equals undefined that means we're at the very bottom of the tree so we can just break
out of this while loop and if it's not undefined we just keep going through until we find the place where
the node that we're moving down the tree is not
more than equal to the left node and is not more than or equal to the right node else if it's only equals two that
Means there should be only one element in the array. So we just cut off the last element else
We reach our null that means there were zero elements than the to begin with and then widgets can return the smallest element
Which is just the element. We just set up here. The last thing I'm going to talk about is this
Now a common use case for the heap data structure is for heap sort
This is one of the most efficient sorting algorithms with average and worst-case performance of o of n log in
heap sort works by taking an unsorted array
Adding each item in the array into a men heap and then extracting every item out of the man heap into a new array
The men heap structure ensures that the new array will contain the original items in least to greatest order
So this is the function that you would use to do that heap sort the hard part is
Creating the all the code. We just already went over and this is just gonna use that code
so let result equals new array while heap that length is more than one we're gonna do with this that remove so we're gonna remove
the
element on top of the tree and we're gonna push onto the result and we're going to keep doing that until we've moved removed all
Of the smallest elements and push it on to the result and it's going to put the elements in order
Well, that's all I'm going to talk about for heaps
feel free to check out this code and create your own heap and and
Add some items and remove some items just to see how it works
The graph data structure is not the same as a graph you may have learned about a math class
Graphs are collections of things and the relationships or connections between them the data in a graph are called nodes or vertices
The connections between the nodes are called edges
One example of graphs is a social network where the nodes are you and other people?
And the edges are whether two people are friends with each other. There are two major types of graphs directed and undirected
Undirected graphs are graphs without any direction on the edges between nodes
directed graphs are graphs with a direction and its edges an
Example of an undirected graph could be a social network
The nodes are people and the edges are friendships an example of a directed graph
Could be the internet and web page links
The nodes are web pages and the directed edges are links to other pages which might not necessarily
Point the other way, I'm going to show you three ways to represent a graph
The first way is called an adjacency list this representation for a graph
Associates each vertex in the graph with the collection of its neighboring vertices or edges in
This image a is connected to B B is connected to a and C and C is connected to B
this is how you could show a
relationship with texts
and
Here is how you could show this adjacency list with JavaScript
This is an undirected graph because it does not show the direction of the edges
This can also be more simply represented as an array where the nodes just have numbers rather than string labels
Another way to represent a graph is to put it in an adjacency
matrix an
adjacency matrix is a two-dimensional array where each nested array has the same number of
Elements as the outer array so it's basically a matrix of numbers where the numbers represent the edges
Zeroes means there is no edge or relationship and ones means there is a relationship
This table shows an adjacency matrix to represent
You can see that the labels for the nodes are on the top and left now. Here's a JavaScript
representation of the same thing
Unlike an adjacency list each row of the matrix has to have the same number of elements as nodes in the graph
here we have a 3 by 3 matrix, which means we have 3 nodes in our graph an
Adjacency matrix can be used to represent a directed graph
Here's a graph for the second node has an edge pointing toward the first node
And then the third node has an edge pointing to the second node notice how the numbers in the array change
There are only ones where a node is pointing toward another node. And since there are only two
Points, there are only two nodes
The final way I will show to represent a graph is an incidence matrix
Like the adjacency matrix an
incidence matrix is a
two-dimensional array, however
the rows and columns means something else here the adjacency matrix use both rows and columns to represent nodes and
Incidence matrix uses roads rose to represent nodes in the columns to represent edges
This means that we can have an uneven number of rows and columns
Each column will represent a unique edge
Also, each edge connects two nodes to show that there is edge between two nodes
You will put a 1 in the two rows of a particular column as you can see in the diagram
Edge one is connected to nodes a and B
Now look at the column for edge 1 in the incidence matrix table
You will see a 1 in both the a row and the B row this shows the edge 1 connects to nodes a and B
here is a directed graph for a directed graph use 1 for an edge leaving a particular node and
Negative 1 for an edge entering a node and here
Is a JavaScript implementation of the incidence matrix?
Graphs can also have weights on their edges so far
We have unweighted edges where just the presence and lack of edges binary 0 or 1
you can have different weights depending on your application a
Different way is represented as a number greater than one
Well now, you know about different types of graphs and how to represent them in JavaScript
I'm gonna talk about how to find the distances between two nodes in a graph
This is one of the main uses of graphs and is called graph traversal
traversal algorithms are algorithms used to traverse or
visit nodes in a graph
The main types of traversal algorithms are breadth-first search and depth-first search in this video
I will be showing how to implement breadth-first search in
JavaScript as
You can see the algorithm starts at one node first visits all its neighbors that are one edge away
Then goes on to visiting each of their neighbors. The point is to determine how close nodes are to a root node
There are different ways to implement breadth-first search in
This version you pass in an adjacency matrix graph and the index of the root node
remember an adjacency matrix each
Nested array in the matrix shows which nodes in the graph are connected to the node at that index
for example
this array is at index 0 so it shows which nodes that node 0 is connected to if
It is connected to a node there is a 1 at that index. But if it is not connected there's a 0 at that index
Before I go through the code, let's see it in action
So here is a graphical representation of this
adjacency graph
Check out my previous graph video to see how this adjacency graph goes into this graph
so we ran the breadth-first search function we passed in this graph up here and
Then we pass then the number 1 so that means we're trying to find out
How far away every node is from the first node?
So you can see this graphical representation of the exact same graph
And if you see the first node right here, that's to know we passed in to the the breadth-first search function
We're gonna see how far away each node is so you can see right here. It shows how far away is
So node 0 is 2 nodes away see because of the direction of the graph. We can't just go straight across as 0
First from one we good at to then we go to zero that's two nodes away one
The the note itself is always zero notes away. And then the second note is one note away
Just one third note is three nodes away. See if first you have to start at one
then you go to 2 then 0 then three, so that's three hops and
Four is infinity because when you're not from the first note, it's impossible to get to the fourth node
Because the fourth note only points back to the first node
This function will output an object of key value pairs
Where a key is the node and the value is its distance from the root
This object will be used to store the distances to the root node
We will start all the distances at infinity which in this version of breadth-first search
Indicates that a node is not reachable from the start node
Here the distance the root node from the root node is set to zero instead of infinity
we are going to create a simple queue to keep track of nodes to visit and
The purpose of this variable is to keep track of the current node that we are traversing
Now we will start a while loop to keep traversing nodes until there are no more nodes in the queue to traverse
We'll start the loop by popping off a node from the queue to traverse
Which at the beginning is the root node?
Here we get all the nodes connected to the current node
Remember each index of the graft is an array that shows what nodes are connected to the root node
Associated with that index. So in this example
we are first looking at node 1 at node 1 the array show is that it is connected to nodes 0 & 2
Now we set the neighbor index variable to an empty array
This will keep track of a list of nodes that are connected to the current node
This lime gets the first note connected to the current node when it says
Index of one this finds the first connected node
Because the number one in our array means that the node is connected to another node at that index
If there is no node with an index of one the index variable will be set to negative one
So while index does not equal negative one, push the index onto our list of neighbors
This line searches for the next connected node
We look for the next one in the array starting after the previous one we found that's what this plus one means
Now that we know all the nodes connected to the current node. We loop through these connecting nodes and get the distance
If the value in the nodes Lin array at the index of the neighbor from the neighbor index array
equals infinity
That means we haven't set the distance of that node yet
So we will set now we are going to set it to the value of the the nodes length array for the current node
plus 1
Then we'll push that neighbor to the queue
so the next time we go through the while loop, we'll check the neighbors of that node to
This for loop is the most complicated part of this and you may have to read through a couple times to completely understand it
at the end we returned the nodes length array and
That's breadth-first search of a graph. Thanks for watching. My name is beau Carnes
Don't forget to subscribe and remember use your code for good