Binary Search Tree - Beau teaches JavaScript

Creating and Maintaining a Binary Search Tree: Understanding the Basics

Instead of 72 pointing to 54 that will be replaced with 54's node, right which is 67 and if there's no node on the right we're going to do the same thing we're going to 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 fifth 17. If you want to replace node 17 you can't just put in 12 here because then what will happen to 23 you can't just put in 23 here cuz then what will happen to 12 so let's look down here at the this picture down here is kind of small let's say we're trying to remove this three 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 three we can place we can replace it with four and then everything will be right with the binary search tree.

So if you look at what it would become over here we just replace the four down here with the three up there but how are we going to get down to that four 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 going to create a temp node which is going to be node. right. So in this case the temp if we're trying to delete the three the temp node would be node. right which would be the six here. No tip node. left does not equal null tip node equals node. left that means we're going to keep first we're going to go to the right of the node we're going to delete and then we're going to keep going to the left until we get to the last one on the left side and this one just happens to before there's no more to go down because you just have to go down one but if there was more to go down it would just keep hopping down and until it got to the most left node now we're going to set node. data to Temp node. data so the node is the three up here so instead of the data of this node being three the data of the node is now four because temp node. data is four now we're going to set node. right to equal and now here we're going to call the remove node function again.

This Is Where It Starts becoming recursive and we're going to pass in the node, the node on the right, and the temp 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 node. data else if data is less than node. data that just means we have to go to the left side of the tree because it's less and here we're going to call we're going to say that node. left equals remove node and we're going to call this recursive function again and pass the node. left and the data and then we're going to return the node else that means data is more than node. data we're do node. write and then call this recursive function again and node. write, data and we're going to return the the node.

So you can see that delete is the most complicated one that we've covered especially when one node has two children 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 going to do const BST = new BST, I've created my binary search tree. We're going to add four, add 2, 6, 1, 3, 57 and then I'm going to remove four and then we're going to f we're going to console.log the Min and the max two times and then we're going to check to see if four is present and another thing we're going to do is I'm going to add in a remove 7 and we'll run that again.

You can see it first it's the minimum is one it's going to console. log Max which is seven but then we remove seven and now the max is going to be six and we're going to see is this present is for present false no four is not present because we've removed it.

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 can do such as finding the tree height and traversing the tree through in order pre-order and post-order traversal if you want to play around with this code you can check the link to the code in the description thanks for watching my name is Bo KS don't forget to subscribe and remember use your code for good

"WEBVTTKind: captionsLanguage: ena 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 visualize 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 see the C here there's fgh 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 node only has two branches also binary search trees are ordered each sub tree is less than or equal to the parent node and each right sub tree 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 uh basically we're going to create two classes the node class and the BST or binary search tree class the node class represents each node in the tree and there's going to be three data properties we have the data which is what we're actually trying to store and we have this. left and this. 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 going to have the add function so this is how we are going to add something to the tree so we're going to 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 going to set the root node to the new no the new data we just put in so new node data so we're just going to create a node based on that data if it's not the first node we're going to 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 we're going to create this function which is search tree where we're going to pass in the node which starts off as the root node if the data we pass in is less than node. data that means we're going to put put the node on the left side of the tree so if the node. left side of the tree is null we're just going to assign node. left to the new node and then we'll return but if node. left is not null we're going to return search tree node. left that just means we're going to continue searching this is where 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 node. data that means we're going to put the node on the right side so if node. right equals equals equals null then we just assign node. write to the new node and we can return else if if the node. right does not equal null we are going to have to keep searching so we're going to return search tree no. WR so else that means data is not less than no. dat data is not more than no. data so they must must be equal if they're equal we're not going to add the data to the tree we're just going to 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 the 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 tree and you want to add 23 first it's going to see that the node 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 node. data which it is because 23 is less than 50 we're going to go to the the node. left if node. 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 node. left does not equal null which is true we are going to return the search tree node. left so we we are now going to run this search tree function but pass in the 17 so now we're going to see does is data less than node. data well now data is 23 but node. data is 17 so this is false now we're going to go down to this is data more than no. data yeah 23 is more than 17 well is node do right null in this example we're saying that 23 isn't there so no. right would be null and then we can just set node. right to be the new node the next functions we're going to talk about are find Min and find Max so we're just going to be finding 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 nine the max is all the way on the right side 76 so just using that knowledge makes it easy to find men and find Max so we're going to set the current node to the root node and so the Min is going to be all the way on the left so while this left does not equal null the current node is going to be current. left and then at the very end it's going to return current. dat so we're going to check this if the left side is not null we're going to go to the next one if it's not null we're going to go to this one if it's not null we're going to go to this one now the next is null because there's nothing to the left of nine so we're going to return current. data we're going to return the nine because that's the data on the very left side find Max is just the same way but the opposite we're going to start at current which is going to be this. Ro which is going to start the the top while current. right does not equal null well this does not equal null cuz it's 72 then we're going to go to the next Loop current equals current. right we're going to go to the next one but now current. right is null because there's nothing to the right of 76 so we can just return current. dat now we have the find function now is present is very similar but instead of returning the node we're just going to return true or false whether the the data is in the tree so we're starting at the to top the root note 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. data return true that means we found it if we haven't found it we're going to see is data less than current. data now current equals current. left so we're going to start searching on the left side else well data must be more than current do 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. data and return true that means it's not in the 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 in the remove function there's going to be a recursive function so we're going to create this function here con remove node equals function where we're going to pass in the node and we're going to pass in the data which is the data what we're what we're trying to remove so we have this whole function here and then here's where we're going to call the function at the end this. root equals remove node and we're going to pass in this. root and data we're assigning this. root to whatever is returned to this function here we're going to 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 see does data equal node. 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 going to do there's actually three different options either node has no children that would be just like the 76 if there's no children we just completely delete that node so if node. left equals null and node. right equals null that means there's no children just return null when we're returning null we're setting the node that had that data to null now we're going to check if the node just has one child if node has no left child if node. left equals null that would be just like this 54 here there's a node on the right but there's no node on the left if node do left equals null then we're just going to return node. right that means we're going to replace this node with whatever is on the right which is 67 so instead of 72 pointing to 54 that will be replaced with 54s node. right which is 67 and if there's no node on the right we're going to do the same thing we're going to 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 fifth 17 if you want to replace node 17 you can't just put in 12 here because then what will happen to 23 you can't just put in 23 here cuz then what will happen to 12 so let's look down here at the this picture down here is kind of small let's say we're trying to remove this three 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 three we can place we can replace it with four and then everything will be right with the binary search Tre so if you look at what it would become over here we just replace the four down here with the three up there but how are we going to get down to that four 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 going to create a temp node which is going to be node. right so in this case the temp if we're trying to delete the three the temp node would be node. right which would be the six here while no tip node. left does not equal null tip node equals node. left that means we're going to keep first we're going to go to the right of the node we're going to delete and then we're going to keep going to the left until we get to the last one one on the left side and this one just happens to before there's no more to go down because you just have to go down one but if there was more to go down it would just keep hopping down and until it got to the most left node now we're going to set node. data to Temp node. data so the node is the three up here so instead of the data of this node being three the data of the node is now four because temp node. data is four now we're going to set node. right to equal and now here we're going to call the remove node function again This Is Where It Starts becoming recursive and we're going to pass in the node the node on the right and the temp 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 node. data else if data is less than node. data that just means we have to go to the left side of the tree because it's less and here we're going to call we're going to say that node. left equals remove node and we're going to call this recursive function again and pass the node. left and the data and then we're going to return the node else that means data is more than node. data we're do node. write and then call this recursive function again and node. write data and we're going to return the the node so you can see that delete 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 going to do const BST equals new BST I've created my binary search tree we're going to add four add 2 6 1 3 57 and then I'm going to remove four and then we're going to f we're going to console.log the Min and the max two times and then we're going to check to see if four is present and another thing we're going to do is I'm going to add in a remove 7 and we'll run that again you can see it first it's the minimum is one it's going to console. log Max which is seven but then we remove seven and now the max is going to be six and we're going to see is this present is for present false no four is not present because we've removed it 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 can do such as finding the tree height and traversing the tree through in order pre-order and post-order traversal if you want to play around with this code you can check the link to the code in the description thanks for watching my name is Bo KS don't forget to subscribe and remember use your code for gooda 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 visualize 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 see the C here there's fgh 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 node only has two branches also binary search trees are ordered each sub tree is less than or equal to the parent node and each right sub tree 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 uh basically we're going to create two classes the node class and the BST or binary search tree class the node class represents each node in the tree and there's going to be three data properties we have the data which is what we're actually trying to store and we have this. left and this. 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 going to have the add function so this is how we are going to add something to the tree so we're going to 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 going to set the root node to the new no the new data we just put in so new node data so we're just going to create a node based on that data if it's not the first node we're going to 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 we're going to create this function which is search tree where we're going to pass in the node which starts off as the root node if the data we pass in is less than node. data that means we're going to put put the node on the left side of the tree so if the node. left side of the tree is null we're just going to assign node. left to the new node and then we'll return but if node. left is not null we're going to return search tree node. left that just means we're going to continue searching this is where 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 node. data that means we're going to put the node on the right side so if node. right equals equals equals null then we just assign node. write to the new node and we can return else if if the node. right does not equal null we are going to have to keep searching so we're going to return search tree no. WR so else that means data is not less than no. dat data is not more than no. data so they must must be equal if they're equal we're not going to add the data to the tree we're just going to 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 the 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 tree and you want to add 23 first it's going to see that the node 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 node. data which it is because 23 is less than 50 we're going to go to the the node. left if node. 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 node. left does not equal null which is true we are going to return the search tree node. left so we we are now going to run this search tree function but pass in the 17 so now we're going to see does is data less than node. data well now data is 23 but node. data is 17 so this is false now we're going to go down to this is data more than no. data yeah 23 is more than 17 well is node do right null in this example we're saying that 23 isn't there so no. right would be null and then we can just set node. right to be the new node the next functions we're going to talk about are find Min and find Max so we're just going to be finding 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 nine the max is all the way on the right side 76 so just using that knowledge makes it easy to find men and find Max so we're going to set the current node to the root node and so the Min is going to be all the way on the left so while this left does not equal null the current node is going to be current. left and then at the very end it's going to return current. dat so we're going to check this if the left side is not null we're going to go to the next one if it's not null we're going to go to this one if it's not null we're going to go to this one now the next is null because there's nothing to the left of nine so we're going to return current. data we're going to return the nine because that's the data on the very left side find Max is just the same way but the opposite we're going to start at current which is going to be this. Ro which is going to start the the top while current. right does not equal null well this does not equal null cuz it's 72 then we're going to go to the next Loop current equals current. right we're going to go to the next one but now current. right is null because there's nothing to the right of 76 so we can just return current. dat now we have the find function now is present is very similar but instead of returning the node we're just going to return true or false whether the the data is in the tree so we're starting at the to top the root note 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. data return true that means we found it if we haven't found it we're going to see is data less than current. data now current equals current. left so we're going to start searching on the left side else well data must be more than current do 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. data and return true that means it's not in the 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 in the remove function there's going to be a recursive function so we're going to create this function here con remove node equals function where we're going to pass in the node and we're going to pass in the data which is the data what we're what we're trying to remove so we have this whole function here and then here's where we're going to call the function at the end this. root equals remove node and we're going to pass in this. root and data we're assigning this. root to whatever is returned to this function here we're going to 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 see does data equal node. 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 going to do there's actually three different options either node has no children that would be just like the 76 if there's no children we just completely delete that node so if node. left equals null and node. right equals null that means there's no children just return null when we're returning null we're setting the node that had that data to null now we're going to check if the node just has one child if node has no left child if node. left equals null that would be just like this 54 here there's a node on the right but there's no node on the left if node do left equals null then we're just going to return node. right that means we're going to replace this node with whatever is on the right which is 67 so instead of 72 pointing to 54 that will be replaced with 54s node. right which is 67 and if there's no node on the right we're going to do the same thing we're going to 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 fifth 17 if you want to replace node 17 you can't just put in 12 here because then what will happen to 23 you can't just put in 23 here cuz then what will happen to 12 so let's look down here at the this picture down here is kind of small let's say we're trying to remove this three 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 three we can place we can replace it with four and then everything will be right with the binary search Tre so if you look at what it would become over here we just replace the four down here with the three up there but how are we going to get down to that four 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 going to create a temp node which is going to be node. right so in this case the temp if we're trying to delete the three the temp node would be node. right which would be the six here while no tip node. left does not equal null tip node equals node. left that means we're going to keep first we're going to go to the right of the node we're going to delete and then we're going to keep going to the left until we get to the last one one on the left side and this one just happens to before there's no more to go down because you just have to go down one but if there was more to go down it would just keep hopping down and until it got to the most left node now we're going to set node. data to Temp node. data so the node is the three up here so instead of the data of this node being three the data of the node is now four because temp node. data is four now we're going to set node. right to equal and now here we're going to call the remove node function again This Is Where It Starts becoming recursive and we're going to pass in the node the node on the right and the temp 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 node. data else if data is less than node. data that just means we have to go to the left side of the tree because it's less and here we're going to call we're going to say that node. left equals remove node and we're going to call this recursive function again and pass the node. left and the data and then we're going to return the node else that means data is more than node. data we're do node. write and then call this recursive function again and node. write data and we're going to return the the node so you can see that delete 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 going to do const BST equals new BST I've created my binary search tree we're going to add four add 2 6 1 3 57 and then I'm going to remove four and then we're going to f we're going to console.log the Min and the max two times and then we're going to check to see if four is present and another thing we're going to do is I'm going to add in a remove 7 and we'll run that again you can see it first it's the minimum is one it's going to console. log Max which is seven but then we remove seven and now the max is going to be six and we're going to see is this present is for present false no four is not present because we've removed it 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 can do such as finding the tree height and traversing the tree through in order pre-order and post-order traversal if you want to play around with this code you can check the link to the code in the description thanks for watching my name is Bo KS don't forget to subscribe and remember use your code for good\n"