1 00:00:00,400 --> 00:00:06,850 ‫So in this video, we're going to go through all of the steps to insert a node into a binary search 2 00:00:06,850 --> 00:00:07,450 ‫tree. 3 00:00:07,660 --> 00:00:10,330 ‫And we're not going to write any code here. 4 00:00:10,330 --> 00:00:12,730 ‫We're just going through the steps. 5 00:00:13,000 --> 00:00:19,570 ‫And then in the next video, we're going to take those steps that we're doing in this video and use 6 00:00:19,570 --> 00:00:22,330 ‫that to help us write the code. 7 00:00:22,660 --> 00:00:29,800 ‫So I'm going to bring up a binary search tree and we're going to insert this node, and you can see 8 00:00:29,800 --> 00:00:31,690 ‫that the node is going to go here. 9 00:00:31,690 --> 00:00:37,180 ‫But we need to go through all the logic of figuring out how to put the node in that spot. 10 00:00:37,720 --> 00:00:42,430 ‫So I'm going to put this back and we're going to document all of the steps. 11 00:00:42,430 --> 00:00:47,710 ‫So on the left, I'm going to add a line here that says Create New Node. 12 00:00:48,010 --> 00:00:54,340 ‫And what I want this video to be is I want it to be similar to the thought process that you go through. 13 00:00:54,340 --> 00:01:00,130 ‫If you just have a piece of paper and you're writing out the steps and trying to figure out how to do 14 00:01:00,130 --> 00:01:01,360 ‫something like this. 15 00:01:01,870 --> 00:01:05,500 ‫So I'm going to take this tree and I'm going to move it over to the right. 16 00:01:05,500 --> 00:01:08,800 ‫So we have more room for our notes on the left. 17 00:01:09,130 --> 00:01:14,980 ‫So the next thing we need to do is compare that 27 node to the route node. 18 00:01:15,310 --> 00:01:20,950 ‫And if the node that we're inserting is less than the root node, we're going to go left. 19 00:01:21,280 --> 00:01:24,970 ‫If the value is greater than then we're going to go right? 20 00:01:25,210 --> 00:01:27,490 ‫So let's add this to our notes. 21 00:01:27,490 --> 00:01:32,290 ‫If it's less than we go left, else, it's greater than and we go right. 22 00:01:32,650 --> 00:01:35,350 ‫So in this case, we're going to go left. 23 00:01:35,650 --> 00:01:38,890 ‫And when we go left, there are two possibilities. 24 00:01:38,890 --> 00:01:48,400 ‫Either the spot to the left of that 47 node is open, in which case we insert the node there or there's 25 00:01:48,400 --> 00:01:55,570 ‫already a node there and which case we have to go down here and compare 27 to this node. 26 00:01:55,930 --> 00:01:57,760 ‫So let's add this to our notes. 27 00:01:57,760 --> 00:02:05,770 ‫We'll say if null pointer and other words, that spot to the left of the 47 is open, we will insert 28 00:02:05,770 --> 00:02:09,580 ‫the new node else we move to the next node. 29 00:02:09,910 --> 00:02:14,650 ‫So now we're going to compare that new node to the 21 node. 30 00:02:14,860 --> 00:02:21,910 ‫And if that new node is less than we go left else, if it's greater, then we go to the right. 31 00:02:22,180 --> 00:02:24,670 ‫So 27 is greater than 21. 32 00:02:24,670 --> 00:02:26,890 ‫So we know we're going to go to the right. 33 00:02:27,690 --> 00:02:35,430 ‫And if 21 to the right is null pointer, in other words, that spot is empty. 34 00:02:35,700 --> 00:02:39,540 ‫We're going to insert that new node like this. 35 00:02:39,960 --> 00:02:47,430 ‫So the thing that should jump out at you is these two if statements were run up here and that we ran 36 00:02:47,430 --> 00:02:53,070 ‫them again down here, so they must be inside of some kind of loop. 37 00:02:53,400 --> 00:02:59,520 ‫And since this is a loop that we don't know how many times it's going to run, it doesn't make sense 38 00:02:59,520 --> 00:03:00,930 ‫to make this a for loop. 39 00:03:01,140 --> 00:03:04,380 ‫It makes sense to make this a while loop. 40 00:03:04,960 --> 00:03:08,860 ‫So now let's take our arrow and move it back up to the top here. 41 00:03:09,190 --> 00:03:13,390 ‫So that arrow is going to be a pointer to a node. 42 00:03:13,390 --> 00:03:15,010 ‫So we need to create that. 43 00:03:15,460 --> 00:03:22,630 ‫This is a variable that will call temp and it is temp that is traversing through the tree. 44 00:03:23,230 --> 00:03:25,360 ‫So let's move this back up here. 45 00:03:25,720 --> 00:03:27,910 ‫We need to have temp start at the top. 46 00:03:27,910 --> 00:03:35,650 ‫So we're going to set it equal to root and this variable needs to be created before we get into that 47 00:03:35,650 --> 00:03:36,610 ‫while loop. 48 00:03:37,060 --> 00:03:41,950 ‫So I'm going to remove these for now and we're going to talk about a couple of our edge cases. 49 00:03:42,250 --> 00:03:49,240 ‫So instead of inserting this 27 node into a tree that has items in it, what if we take the 27 node 50 00:03:49,240 --> 00:03:53,230 ‫and we're trying to insert this into an empty tree? 51 00:03:53,350 --> 00:03:58,300 ‫In this case, we just want root to be equal to the new node. 52 00:03:58,720 --> 00:04:03,010 ‫And if we're doing this, we don't even need that temp variable. 53 00:04:03,220 --> 00:04:06,220 ‫So this code even goes above that. 54 00:04:06,640 --> 00:04:12,880 ‫If root equals null pointer, then we want to set root to be equal to new node. 55 00:04:13,300 --> 00:04:16,240 ‫So now let's put the tree back the way it was. 56 00:04:16,240 --> 00:04:23,740 ‫And let's say instead of inserting a 27 node, we're going to insert a 76 node. 57 00:04:24,160 --> 00:04:25,690 ‫We're always going to start at the top. 58 00:04:25,690 --> 00:04:29,680 ‫We're going to compare it to that 47 node 76 is greater than. 59 00:04:29,680 --> 00:04:33,670 ‫So we go to the right and this is where we have the problem. 60 00:04:34,000 --> 00:04:38,190 ‫You can't have duplicate values in a binary search tree. 61 00:04:38,200 --> 00:04:41,620 ‫It either has to be greater than or less than. 62 00:04:42,190 --> 00:04:46,000 ‫So we're going to insert this line into the while loop. 63 00:04:46,010 --> 00:04:51,850 ‫If new node is ever equal to temp return false. 64 00:04:52,180 --> 00:04:59,650 ‫And this has to go inside of the while loop because we have to compare that new node with each node 65 00:04:59,650 --> 00:05:02,080 ‫as we're traversing through the tree. 66 00:05:02,590 --> 00:05:09,550 ‫And with this edge case, these are all of the steps to be able to insert a node. 67 00:05:09,940 --> 00:05:16,720 ‫So we're going to pick up right here in the next video and use these steps to help us write all of the 68 00:05:16,720 --> 00:05:20,500 ‫code to insert a node into a binary search tree. 69 00:05:21,010 --> 00:05:25,360 ‫But for now, that is our introduction to insert.