‫So in this video, we're going to go through all of the steps to insert a node into a binary search
‫tree.
‫And we're not going to write any code here.
‫We're just going through the steps.
‫And then in the next video, we're going to take those steps that we're doing in this video and use
‫that to help us write the code.
‫So I'm going to bring up a binary search tree and we're going to insert this node, and you can see
‫that the node is going to go here.
‫But we need to go through all the logic of figuring out how to put the node in that spot.
‫So I'm going to put this back and we're going to document all of the steps.
‫So on the left, I'm going to add a line here that says Create New Node.
‫And what I want this video to be is I want it to be similar to the thought process that you go through.
‫If you just have a piece of paper and you're writing out the steps and trying to figure out how to do
‫something like this.
‫So I'm going to take this tree and I'm going to move it over to the right.
‫So we have more room for our notes on the left.
‫So the next thing we need to do is compare that 27 node to the route node.
‫And if the node that we're inserting is less than the root node, we're going to go left.
‫If the value is greater than then we're going to go right?
‫So let's add this to our notes.
‫If it's less than we go left, else, it's greater than and we go right.
‫So in this case, we're going to go left.
‫And when we go left, there are two possibilities.
‫Either the spot to the left of that 47 node is open, in which case we insert the node there or there's
‫already a node there and which case we have to go down here and compare 27 to this node.
‫So let's add this to our notes.
‫We'll say if null pointer and other words, that spot to the left of the 47 is open, we will insert
‫the new node else we move to the next node.
‫So now we're going to compare that new node to the 21 node.
‫And if that new node is less than we go left else, if it's greater, then we go to the right.
‫So 27 is greater than 21.
‫So we know we're going to go to the right.
‫And if 21 to the right is null pointer, in other words, that spot is empty.
‫We're going to insert that new node like this.
‫So the thing that should jump out at you is these two if statements were run up here and that we ran
‫them again down here, so they must be inside of some kind of loop.
‫And since this is a loop that we don't know how many times it's going to run, it doesn't make sense
‫to make this a for loop.
‫It makes sense to make this a while loop.
‫So now let's take our arrow and move it back up to the top here.
‫So that arrow is going to be a pointer to a node.
‫So we need to create that.
‫This is a variable that will call temp and it is temp that is traversing through the tree.
‫So let's move this back up here.
‫We need to have temp start at the top.
‫So we're going to set it equal to root and this variable needs to be created before we get into that
‫while loop.
‫So I'm going to remove these for now and we're going to talk about a couple of our edge cases.
‫So instead of inserting this 27 node into a tree that has items in it, what if we take the 27 node
‫and we're trying to insert this into an empty tree?
‫In this case, we just want root to be equal to the new node.
‫And if we're doing this, we don't even need that temp variable.
‫So this code even goes above that.
‫If root equals null pointer, then we want to set root to be equal to new node.
‫So now let's put the tree back the way it was.
‫And let's say instead of inserting a 27 node, we're going to insert a 76 node.
‫We're always going to start at the top.
‫We're going to compare it to that 47 node 76 is greater than.
‫So we go to the right and this is where we have the problem.
‫You can't have duplicate values in a binary search tree.
‫It either has to be greater than or less than.
‫So we're going to insert this line into the while loop.
‫If new node is ever equal to temp return false.
‫And this has to go inside of the while loop because we have to compare that new node with each node
‫as we're traversing through the tree.
‫And with this edge case, these are all of the steps to be able to insert a node.
‫So we're going to pick up right here in the next video and use these steps to help us write all of the
‫code to insert a node into a binary search tree.
‫But for now, that is our introduction to insert.