1
00:00:00,470 --> 00:00:06,590
‫So now we're going to write the code for our insert function and we're going to pick up where we left

2
00:00:06,590 --> 00:00:11,930
‫off in the last video with all the steps to create this function.

3
00:00:12,290 --> 00:00:15,020
‫So I'm going to move these steps to the bottom.

4
00:00:15,320 --> 00:00:20,130
‫So we have room for our code and we'll start our function off like this.

5
00:00:20,150 --> 00:00:21,490
‫It's called insert.

6
00:00:21,500 --> 00:00:23,180
‫We pass it a value.

7
00:00:23,510 --> 00:00:28,010
‫So our first step on our list is that we're going to create a node.

8
00:00:28,460 --> 00:00:35,270
‫So we'll do that with this line of code, and now we can remove this from our list.

9
00:00:35,840 --> 00:00:42,350
‫So then we'll say if root is equal to null pointer, then we're going to set root to be equal to the

10
00:00:42,350 --> 00:00:43,370
‫new node.

11
00:00:43,700 --> 00:00:47,800
‫That is this situation when we have an empty tree.

12
00:00:47,810 --> 00:00:51,860
‫When this happens, we just want to set root to be equal to the new node.

13
00:00:51,860 --> 00:00:54,230
‫And we'll do that like this.

14
00:00:54,410 --> 00:00:59,540
‫If root equals null pointer, then root equals new node.

15
00:00:59,870 --> 00:01:05,450
‫But because this has inserted the node, we don't want to continue running code.

16
00:01:05,450 --> 00:01:09,380
‫So we're going to have a return statement where we say Return.

17
00:01:09,380 --> 00:01:10,160
‫True.

18
00:01:10,550 --> 00:01:17,390
‫So now we can remove this from the list and then we'll create a variable temp that we set equal to root.

19
00:01:17,420 --> 00:01:22,970
‫We'll do it like this, and then we can remove this item from our list.

20
00:01:23,790 --> 00:01:26,280
‫And that brings us to our wild loop.

21
00:01:26,520 --> 00:01:32,850
‫So with our wild loop, we're just going to say while true now there are two ways to break out of a

22
00:01:32,850 --> 00:01:33,650
‫wild loop.

23
00:01:33,660 --> 00:01:40,980
‫You can have the conditional at some point be false, which of course can never happen here because

24
00:01:40,980 --> 00:01:43,230
‫we have it set to true.

25
00:01:43,680 --> 00:01:48,990
‫The other way you can break out of a while loop is with a return statement and that's what we are going

26
00:01:48,990 --> 00:01:50,460
‫to be doing here.

27
00:01:50,940 --> 00:01:53,400
‫So I'll remove this from the list.

28
00:01:53,820 --> 00:01:58,380
‫And now we'll say if new node equals temp return false.

29
00:01:58,590 --> 00:02:05,610
‫That is this situation where you have a know that you're trying to insert where that value is already

30
00:02:05,610 --> 00:02:06,540
‫in the tree.

31
00:02:06,900 --> 00:02:09,450
‫So we'll do that with this line of code.

32
00:02:09,600 --> 00:02:16,770
‫And I want you to notice that in the notes I said new node, but here I have new node value.

33
00:02:16,770 --> 00:02:21,990
‫We're not really comparing the nodes, we're comparing the value in the nodes.

34
00:02:22,470 --> 00:02:26,550
‫And if those are ever equal, we return false.

35
00:02:27,060 --> 00:02:29,970
‫So now we can remove this from our list.

36
00:02:30,510 --> 00:02:36,060
‫And now we'll say if the node we're inserting is less, then we're going to go left.

37
00:02:36,060 --> 00:02:39,090
‫Else it's greater than and we're going to go right.

38
00:02:39,360 --> 00:02:41,310
‫So we'll do that with this.

39
00:02:41,310 --> 00:02:46,170
‫And notice once again, we're comparing the values from these nodes.

40
00:02:46,650 --> 00:02:48,720
‫So you can see we're running out of room here.

41
00:02:48,720 --> 00:02:51,740
‫So I'm going to take this if statement and move it up.

42
00:02:51,750 --> 00:02:59,160
‫But before we do, I want you to remember that this exists inside of this wild loop.

43
00:02:59,760 --> 00:03:01,860
‫So I'm going to move this up.

44
00:03:02,380 --> 00:03:09,430
‫So these two if statements are nested one inside of another, and it's going to be easier to explain

45
00:03:09,430 --> 00:03:10,390
‫this with a code.

46
00:03:10,390 --> 00:03:14,350
‫So I'm going to go ahead and remove these two and code this out.

47
00:03:14,860 --> 00:03:20,170
‫So I'm going to bring up this tree and we're going to insert this node.

48
00:03:20,680 --> 00:03:26,680
‫And remember, we're going to have this temp variable pointing at that root node to begin with.

49
00:03:27,040 --> 00:03:35,530
‫So now with this if statement, we're wanting to compare the value from this new node to the value of

50
00:03:35,530 --> 00:03:38,500
‫the node that temp is pointing to.

51
00:03:38,890 --> 00:03:45,490
‫So if the new node value is less than the temp value, we want to go to the left.

52
00:03:45,760 --> 00:03:49,900
‫And when we go to the left, there are two possibilities.

53
00:03:49,900 --> 00:03:59,350
‫Either that spot to the left is open and we insert that right there or that spot is not open and we

54
00:03:59,350 --> 00:04:01,720
‫need to move down to the next node.

55
00:04:02,050 --> 00:04:08,260
‫So we're going to write code for this situation first where that is open and this is where we do that

56
00:04:08,260 --> 00:04:15,250
‫nested if statement if temp left equals null pointer and that's the way it is here, that means that

57
00:04:15,250 --> 00:04:17,470
‫spot is open to the left.

58
00:04:17,890 --> 00:04:22,150
‫Then we want to set temp left to be equal to new node.

59
00:04:22,150 --> 00:04:26,710
‫That is temp left equals new node.

60
00:04:27,040 --> 00:04:31,750
‫And because we have placed that node, we're going to return.

61
00:04:31,750 --> 00:04:36,370
‫True in this return statement is what breaks us out of that while loop.

62
00:04:36,820 --> 00:04:41,560
‫So now let's code for our other situation when we have an item here.

63
00:04:41,860 --> 00:04:51,040
‫In this case we're going to say temp equals temp left, that is temp left and that moves temp down to

64
00:04:51,040 --> 00:04:51,610
‫here.

65
00:04:51,820 --> 00:04:59,440
‫And remember, this is in a while loop and it's going to run again and now temp left is equal to null

66
00:04:59,440 --> 00:05:00,100
‫pointer.

67
00:05:00,100 --> 00:05:09,940
‫So we're going to set temp left to be equal to new node like this and then we will return.

68
00:05:09,940 --> 00:05:10,750
‫True.

69
00:05:11,290 --> 00:05:18,460
‫So let's move temp back up to the top and look at how we do this on the other side of the binary search

70
00:05:18,460 --> 00:05:22,090
‫tree when the node that we're adding is greater than.

71
00:05:22,390 --> 00:05:24,220
‫So I'm going to move this tree over.

72
00:05:24,220 --> 00:05:30,130
‫So we have room to work on the right and in our code we're going to say else.

73
00:05:30,430 --> 00:05:36,310
‫And the node that we're going to insert into the tree is that 82 node on the lower right.

74
00:05:36,310 --> 00:05:37,720
‫I'll remove that.

75
00:05:37,960 --> 00:05:43,960
‫And just like we did before, we're going to start with that spot on the right of the root node being

76
00:05:43,960 --> 00:05:52,600
‫open and we'll say if temp right equals null pointer, which means that spot on the right of that root

77
00:05:52,600 --> 00:05:53,800
‫node is open.

78
00:05:54,650 --> 00:05:58,070
‫We're going to set temp right to be equal to new node.

79
00:05:58,070 --> 00:06:00,380
‫That is temp, right?

80
00:06:00,410 --> 00:06:02,330
‫Equals new node.

81
00:06:02,660 --> 00:06:06,800
‫And because we've placed the node, we need to have a return statement.

82
00:06:07,280 --> 00:06:08,540
‫So we'll return.

83
00:06:08,540 --> 00:06:09,320
‫True.

84
00:06:09,740 --> 00:06:12,590
‫So that's our code if that spot was open.

85
00:06:12,590 --> 00:06:18,020
‫But if there was a node in that spot, we would say temp equals temp.

86
00:06:18,020 --> 00:06:18,800
‫Right.

87
00:06:19,010 --> 00:06:20,660
‫That is temp.

88
00:06:21,290 --> 00:06:24,410
‫Right and that moves temp down.

89
00:06:24,830 --> 00:06:32,480
‫And because all of this is in the wild loop, this runs again and now temp right is equal to null pointer.

90
00:06:32,750 --> 00:06:40,400
‫So we set temp right to be equal to new node that is temp right equals new node.

91
00:06:40,730 --> 00:06:46,850
‫And because we placed the node, we need to have a return statement and we return.

92
00:06:46,880 --> 00:06:47,720
‫True.

93
00:06:48,320 --> 00:06:52,760
‫So this is the hard part of the insert function.

94
00:06:53,600 --> 00:06:55,940
‫So now let's bring back our wild loop.

95
00:06:55,940 --> 00:06:59,960
‫And inside of this wild loop, we have this if statement.

96
00:06:59,990 --> 00:07:04,100
‫This test to make sure that this isn't a duplicate value.

97
00:07:04,610 --> 00:07:14,090
‫And this is if the new node's value is less than we go left and this is if the new nodes value is greater

98
00:07:14,090 --> 00:07:16,160
‫than and we go right.

99
00:07:16,700 --> 00:07:25,760
‫So now this add this while loop in with the rest of our code and that is the entire insert function.

100
00:07:26,210 --> 00:07:33,740
‫So we'll look at this code in a moment and vs code and when we do we'll build this tree and then we'll

101
00:07:33,740 --> 00:07:43,400
‫insert a node with a value of 27 and then we'll print out the node that is root left, right.

102
00:07:43,760 --> 00:07:50,360
‫So you start at the 47 node, that's the root and then left and right, and that should be the 27 node.

103
00:07:50,780 --> 00:07:54,650
‫So now let's flip over to VS Code and take a look at this.

104
00:07:55,250 --> 00:08:02,870
‫So there is our insert member function added to our binary search tree class and I'll scroll up.

105
00:08:03,350 --> 00:08:10,760
‫So we'll run these lines to create that tree that we just saw and then we'll run, insert one more time

106
00:08:10,760 --> 00:08:17,360
‫on the number 27 and then in this C out statement in our binary search tree, we're going to do root

107
00:08:17,360 --> 00:08:21,410
‫left right and print out that node.

108
00:08:22,110 --> 00:08:30,420
‫And remember to do this, you have to have route set to public, so make sure you do that.

109
00:08:30,420 --> 00:08:33,300
‫Otherwise you won't be able to print this out.

110
00:08:33,600 --> 00:08:34,920
‫So I'll run this.

111
00:08:35,880 --> 00:08:39,650
‫And you can see up here, this gives us an address to a node.

112
00:08:39,660 --> 00:08:43,110
‫So I'm going to come up here and add value to this.

113
00:08:45,340 --> 00:08:47,290
‫And now I'll run this again.

114
00:08:48,190 --> 00:08:51,910
‫And you can see that this has returned our 27 node.

115
00:08:52,620 --> 00:08:57,810
‫So it looks like we have a working function for insert.