1
00:00:01,890 --> 00:00:10,050
OK, so then to another video in this video, we're actually going to go ahead and implement our binary

2
00:00:10,050 --> 00:00:16,790
search tree and put just a few basic functions into the implementation like insert.

3
00:00:16,800 --> 00:00:23,550
Of course, we all need to create it and we'll have a find function and then we might do a sort of an

4
00:00:23,550 --> 00:00:28,710
order traversal that will print out all of the values in order.

5
00:00:30,100 --> 00:00:33,100
And we might add another function, we'll see.

6
00:00:33,730 --> 00:00:40,900
But I have created a new project here, I'm just calling it BFD Record because I'm doing this recording

7
00:00:40,900 --> 00:00:48,790
for this, but you can go ahead and open up a new project in theline and just call it whatever you want

8
00:00:50,020 --> 00:00:53,740
and went ahead and made a main file here, which I will be tweeting this at some point.

9
00:00:53,740 --> 00:00:58,660
But I'm telling you this line, of course, and putting my own values in the client file.

10
00:00:59,500 --> 00:01:06,700
But to get started, I'm going to go ahead and make a node class similar to how we did with the linked

11
00:01:06,700 --> 00:01:07,220
list.

12
00:01:07,270 --> 00:01:13,570
We're going to need nodes with pointers to make our binary search tree, so we're gonna need that left

13
00:01:13,570 --> 00:01:14,380
pointer right pointer.

14
00:01:14,500 --> 00:01:15,970
Let's go ahead and get started on that.

15
00:01:18,030 --> 00:01:30,030
So we go here and make a new C++ header file, and I am going to call this tree node.

16
00:01:31,730 --> 00:01:33,860
Yeah, someone neutrino.

17
00:01:36,520 --> 00:01:37,060
H.

18
00:01:38,110 --> 00:01:49,480
And I'm not sure if you will have gone over this by now, but what I'm going to do is actually put my

19
00:01:49,480 --> 00:01:52,740
implementation here in the header file.

20
00:01:54,060 --> 00:02:01,110
So you may already be familiar with this, but just in case you're not, you can put your implementation

21
00:02:01,110 --> 00:02:07,890
in the header file as well, and I'm going to do this with a sort of more modern syntax for my constructor.

22
00:02:09,180 --> 00:02:15,720
I am going to use a I'm actually out two constructors and I'm going to use an initialization list for

23
00:02:15,720 --> 00:02:15,960
that.

24
00:02:16,680 --> 00:02:20,160
So let's go ahead and see how this will work.

25
00:02:21,300 --> 00:02:30,690
So in my public section, I'm going to put a constructor here and then I'm going to do something like

26
00:02:30,690 --> 00:02:31,230
this.

27
00:02:31,770 --> 00:02:35,040
I'm going to need a left and right

28
00:02:38,130 --> 00:02:41,950
pointer here, and I'm initialize them like this and these parentheses.

29
00:02:41,950 --> 00:02:47,010
So I'm going to say no pointer, right is null pointer.

30
00:02:48,030 --> 00:02:51,480
And then I'm also going to need my data, just like the link list.

31
00:02:51,480 --> 00:02:57,180
And so this will be my data member and I will initialize at the same as well initialize it to zero because

32
00:02:57,180 --> 00:03:01,950
we're just going to be storing integer values in this tree and then you finish off the initialization

33
00:03:01,950 --> 00:03:06,570
list with just some empty brackets like that.

34
00:03:08,850 --> 00:03:14,040
And it's probably as complaining because we didn't make those memories yet, so I'm just going to make

35
00:03:14,040 --> 00:03:21,660
those right now, I'm going to say these are going to be tape trino the pointer.

36
00:03:22,440 --> 00:03:33,410
So I am going to say to, you know, point her left and right and then my data is going to be an integer.

37
00:03:33,420 --> 00:03:37,710
I'm actually going to call that underscore data just like I did up there.

38
00:03:38,580 --> 00:03:41,790
OK, so yeah, this is kind of a different syntax, of course.

39
00:03:41,790 --> 00:03:43,560
Like I said, you might have already seen this.

40
00:03:43,740 --> 00:03:48,980
This is an initialization list is just another way to write your constructor here.

41
00:03:48,990 --> 00:03:59,850
So I'm also going to have another constructor that is able to take an integer already like a value and

42
00:04:00,480 --> 00:04:07,680
initialize a tree with that first initialize a node with that value.

43
00:04:07,690 --> 00:04:12,630
So it's going to be another initialization list.

44
00:04:12,780 --> 00:04:17,550
So I'm going to do the same thing and say left and right are no points here,

45
00:04:21,510 --> 00:04:30,030
but then data is going to be set to the past integer, and I actually didn't even add that in there

46
00:04:30,030 --> 00:04:30,510
in my bed.

47
00:04:32,700 --> 00:04:33,230
Do it.

48
00:04:33,240 --> 00:04:36,840
And so there we go.

49
00:04:37,050 --> 00:04:40,310
So now we have a second constructor there.

50
00:04:41,580 --> 00:04:52,500
I'm going to make a function that returns my left pointer, which is going to be I'm going to call this

51
00:04:52,500 --> 00:04:53,670
left sub tree.

52
00:04:53,670 --> 00:04:59,070
So as you saw in the if you can think back to the drawing of the binary search tree, I'm going to want

53
00:04:59,070 --> 00:05:02,490
some getters on.

54
00:05:03,850 --> 00:05:07,810
And setters, similar to how we had for the link list we had.

55
00:05:07,810 --> 00:05:08,920
Previous Next.

56
00:05:09,310 --> 00:05:14,620
This is going to be very similar, but it's going to be called left cemetery and right cemetery because

57
00:05:14,620 --> 00:05:20,140
it's going to give you access from a given node to that nodes left cemetery and right cemetery will

58
00:05:20,140 --> 00:05:26,290
be able to do some setting and getting these values.

59
00:05:26,290 --> 00:05:28,300
So let's go ahead and do that.

60
00:05:29,980 --> 00:05:32,470
So I'm glad you left cemetery.

61
00:05:32,920 --> 00:05:35,420
And this is going to return.

62
00:05:35,510 --> 00:05:36,790
He left.

63
00:05:39,460 --> 00:05:46,350
And then I'm going to say tree nude, right, some tree.

64
00:05:47,860 --> 00:05:52,480
And this is going to return, right?

65
00:05:55,370 --> 00:06:03,740
And then I'm going to put these centers here, so I'm going to say left Sochi is going to be void and

66
00:06:03,740 --> 00:06:06,390
passing a tree node and now.

67
00:06:06,410 --> 00:06:12,860
So while I'm doing this, just remember back to what we did for a linked list because it's very similar

68
00:06:14,120 --> 00:06:16,340
and I'm actually going to just declare.

69
00:06:19,280 --> 00:06:27,530
This object to that calling object in here, and I must say this arrow left equals left, so that'll

70
00:06:27,540 --> 00:06:33,230
be able to set a node left pointer correctly

71
00:06:36,920 --> 00:06:39,620
and I will say right some tree.

72
00:06:40,010 --> 00:06:44,120
So this is just like some overloaded functions here, I guess.

73
00:06:44,120 --> 00:06:47,420
Not really, since they return different values, but kind of like that.

74
00:06:49,660 --> 00:06:50,360
So

75
00:06:55,280 --> 00:06:57,550
I'm going to do the same thing, right?

76
00:06:57,590 --> 00:07:01,460
I'm going to say this arrow right equals right.

77
00:07:01,620 --> 00:07:02,570
I'm just past doing.

78
00:07:04,360 --> 00:07:04,750
Cool.

79
00:07:05,200 --> 00:07:13,960
So that sets a note left and right some trees and also retrieves a node's left and right, some trees.

80
00:07:14,080 --> 00:07:16,690
So we're all set up with that.

81
00:07:16,930 --> 00:07:19,690
And then of course, I'm going to do that.

82
00:07:20,280 --> 00:07:27,670
Get her combo with this ampersand to be able to return our data like we have already done before as

83
00:07:27,670 --> 00:07:27,940
well.

84
00:07:31,450 --> 00:07:31,900
All right.

85
00:07:32,290 --> 00:07:37,910
And that is actually all we're going to have here for our node class.

86
00:07:37,930 --> 00:07:38,650
It's kind of nice.

87
00:07:38,650 --> 00:07:40,170
That's why I wanted to do it this way.

88
00:07:40,180 --> 00:07:43,150
It's just nice and compact here.

89
00:07:43,150 --> 00:07:49,240
We have just a header file with our implementation and now we have a full binary search tree node class

90
00:07:49,240 --> 00:07:49,660
setup.

91
00:07:50,950 --> 00:07:55,090
OK, so let's move on to the next part, which is the actual tree.

92
00:07:55,900 --> 00:08:01,180
So if we're still using a comparison to the link lists that we've done, we would have made the L.A.

93
00:08:01,180 --> 00:08:02,020
class now.

94
00:08:02,020 --> 00:08:06,780
But it was our tree node and we have to make our actual link list class.

95
00:08:06,790 --> 00:08:08,360
And so same for the tree.

96
00:08:08,380 --> 00:08:11,590
We're going to have to make our binary search tree class now.

97
00:08:11,890 --> 00:08:13,480
So let's go ahead and make that.

98
00:08:15,300 --> 00:08:17,760
So this is going to be a C++.

99
00:08:17,980 --> 00:08:26,700
Actually, I'm going to make the header first and I'm going to do the header file here, so I'm just

100
00:08:26,700 --> 00:08:29,580
going to call this beast from binary search tree.

101
00:08:34,560 --> 00:08:34,910
All right.

102
00:08:35,460 --> 00:08:51,320
So I'm, of course, going to want to include my tree node tree node h and then I am going to be using

103
00:08:51,600 --> 00:08:52,710
namespace

104
00:08:55,710 --> 00:09:00,360
D, Class B s t d public.

105
00:09:00,630 --> 00:09:04,680
I do my constructor here and this one, I'm going to have an implementation file.

106
00:09:04,890 --> 00:09:07,200
So I'm just going to leave this here like a prototype.

107
00:09:07,860 --> 00:09:14,820
I'm going to put my destructor didn't do that in the node, but I'm going to do it right here right

108
00:09:14,820 --> 00:09:15,180
now.

109
00:09:17,730 --> 00:09:19,380
So we'll do an insert function.

110
00:09:19,380 --> 00:09:21,030
We're going to have to insert a value.

111
00:09:22,150 --> 00:09:27,180
When I make a Boolean function that tells us whether something exists in the tree, we're going to pass

112
00:09:27,180 --> 00:09:32,520
a value to it and it's just going to be called find so we can find a value to see if there that value

113
00:09:32,520 --> 00:09:33,840
in fact exists in the tree.

114
00:09:36,900 --> 00:09:41,880
Then I am going to do a size function.

115
00:09:44,890 --> 00:09:45,790
So we'll do that.

116
00:09:47,440 --> 00:09:48,180
Going to do.

117
00:09:49,030 --> 00:09:52,840
In order down of the tree is what I'm going to call this.

118
00:09:52,840 --> 00:09:54,490
This will be our in order traversal.

119
00:09:54,640 --> 00:09:57,160
So I'm just like, you know, you dumped the values of the tree.

120
00:09:59,590 --> 00:10:06,040
I'm going to do only those functions for later.

121
00:10:06,460 --> 00:10:11,890
Actually, yeah, I might actually do another fine here.

122
00:10:15,280 --> 00:10:16,560
So I'm going to do it.

123
00:10:16,990 --> 00:10:20,080
We might go over an introduce one and we'll go ahead and just do that right now.

124
00:10:20,090 --> 00:10:24,250
We may get to implementing that today might be in the video, but only go ahead with that here.

125
00:10:27,060 --> 00:10:33,870
OK, and the thing is, is that we're actually going to have to make another version of a lot of these

126
00:10:34,020 --> 00:10:43,320
functions because we're going to be calling it from the client file, like calling each of these functions

127
00:10:43,320 --> 00:10:44,670
that we wrote here.

128
00:10:45,210 --> 00:10:52,980
But since a lot of them are going to have a starting at a root node member here, as you'll see that

129
00:10:52,980 --> 00:11:00,540
I'll actually go ahead and just do that right now, I'm going to make a type tree node pointer that's

130
00:11:00,540 --> 00:11:02,310
going to represent the root of the tree.

131
00:11:02,310 --> 00:11:03,390
So that top value.

132
00:11:03,390 --> 00:11:08,700
If you think back to our picture of the binary search tree, I believe it started at 10 or something

133
00:11:08,700 --> 00:11:09,360
in that lecture.

134
00:11:10,080 --> 00:11:12,210
It'll just that was our roots.

135
00:11:12,210 --> 00:11:14,790
So we're going to need to make a root and pointer for root.

136
00:11:15,960 --> 00:11:19,470
And then I'm also going to have size here as well.

137
00:11:22,010 --> 00:11:28,260
And so, like I was just saying, these will be what we're going to be calling our client file.

138
00:11:28,280 --> 00:11:32,180
But since we want to start it through, we're going to make another function.

139
00:11:32,180 --> 00:11:38,270
So each one of these will call another function that does the actual work, and it'll be passed the

140
00:11:38,270 --> 00:11:46,190
root node quite often, so it can start at the root node to do the recursion and go through the tree.

141
00:11:46,670 --> 00:11:48,770
So that's why we're going to have like multiple versions.

142
00:11:48,770 --> 00:11:55,430
We're going to use encapsulation to make sure our client file is just accessing them by passing a value

143
00:11:55,430 --> 00:11:58,550
or just calling it without a parameter or argument.

144
00:11:59,600 --> 00:12:05,540
And then the actual work that references our private data member route will be done in another function.

145
00:12:07,580 --> 00:12:16,070
So I'm going to say tree node pointer to be returned by this insert function and it'll take this tree

146
00:12:16,070 --> 00:12:16,520
node.

147
00:12:16,610 --> 00:12:23,060
I'm just going to call node that would be representative of the root value.

148
00:12:23,690 --> 00:12:34,010
And then I'm just going to say and be there for the value, then I'm going to have my size function.

149
00:12:34,700 --> 00:12:36,530
I'm going to actually, it's my fine.

150
00:12:36,530 --> 00:12:52,700
So at that find it's going to be a boolean actually ran find tree node node in the value and then I

151
00:12:52,700 --> 00:12:54,560
am going to do my size.

152
00:12:54,860 --> 00:12:58,070
So my size function as a tree node

153
00:13:00,620 --> 00:13:01,190
node

154
00:13:04,940 --> 00:13:05,780
was just node.

155
00:13:06,680 --> 00:13:08,420
Yeah, OK.

156
00:13:08,420 --> 00:13:13,550
And then I'm going to do my in order dumbed

157
00:13:17,230 --> 00:13:23,690
down and we will take you to node known, which will be the roots.

158
00:13:25,370 --> 00:13:25,720
OK.

159
00:13:26,690 --> 00:13:33,680
So I think I have them on there except for it or find I did not do that.

160
00:13:36,880 --> 00:13:40,270
So, yeah, well, I'm not sure whether I'm going to do that 100 percent yet, but I'm just going to

161
00:13:40,270 --> 00:13:41,320
leave it in the header there.

162
00:13:41,470 --> 00:13:42,520
We might get into that.

163
00:13:42,520 --> 00:13:43,090
We might not.

164
00:13:43,870 --> 00:13:46,120
So I'll just keep it like that.

165
00:13:47,220 --> 00:13:51,660
So let's go ahead and go to our implementation file.

166
00:13:54,170 --> 00:13:56,390
OK, so I go up here.

167
00:13:58,320 --> 00:14:05,050
I'm going to make a sauce file and I'm going to call this GST.

168
00:14:05,790 --> 00:14:06,800
That's BP.

169
00:14:11,120 --> 00:14:11,480
OK.

170
00:14:12,530 --> 00:14:19,130
So go ahead and make that constructor actually going to include myself for first.

171
00:14:21,340 --> 00:14:25,520
So this is going to be three known going to need A..

172
00:14:25,540 --> 00:14:30,730
And then, of course, our current head in that we've just made so you h.

173
00:14:33,140 --> 00:14:41,070
And then I think we're just going to include extreme here by reprinting some stuff out.

174
00:14:41,090 --> 00:14:41,660
I think.

175
00:14:43,060 --> 00:14:45,490
And that is all I'll include for now.

176
00:14:46,360 --> 00:14:48,070
Do you say namespace?

177
00:14:49,750 --> 00:14:53,740
Let's go ahead and make our constructor here.

178
00:14:56,060 --> 00:15:07,190
So we will say ridge equals no pointer size equals zero.

179
00:15:10,910 --> 00:15:20,360
And then for my destructor, it's just going to be like a default saying, so I'm actually going to

180
00:15:20,390 --> 00:15:23,630
take this suggestion here and just do that.

181
00:15:25,920 --> 00:15:38,420
And let's see, we have our concert and my concert function is going to actually use.

182
00:15:38,480 --> 00:15:41,030
I think I'm actually going to use my fine function.

183
00:15:41,030 --> 00:15:43,040
So let's do that first, actually.

184
00:15:44,900 --> 00:15:45,770
So.

185
00:15:47,030 --> 00:15:55,620
It's kind of me a little bit out of order, but it should still work out, so I'm going to do.

186
00:15:57,840 --> 00:16:06,560
This find, and I'm going to say to me, no, no.

187
00:16:09,280 --> 00:16:14,780
And the lips red tomasello.

188
00:16:17,670 --> 00:16:25,470
So I'm actually going to do this, this is a client find, and I'm going to just return find, is this

189
00:16:25,500 --> 00:16:29,700
going to call the other find that passes root and the value?

190
00:16:30,660 --> 00:16:33,150
And then I'll do my actual implementation right here.

191
00:16:35,490 --> 00:16:41,940
So I'll have the tree node cleaner and which will be a root because you can see it's been passed there

192
00:16:41,940 --> 00:16:44,460
and then I'll have the value being passed as well.

193
00:16:47,820 --> 00:16:51,250
And so let's look at how we would do this find function.

194
00:16:51,300 --> 00:17:00,180
So we're going to need a base case and our base case is going to be if the node, which would be originally

195
00:17:00,180 --> 00:17:07,230
that route planner in this past will be traversing different nodes and going to say if node is equal

196
00:17:07,230 --> 00:17:11,940
to no pointer then and actually, I don't need those brackets.

197
00:17:11,940 --> 00:17:13,770
I'm just going to say return false.

198
00:17:17,730 --> 00:17:20,550
Then what we want to do is define nodes.

199
00:17:21,000 --> 00:17:27,450
Data is equal to the value that was passed.

200
00:17:28,470 --> 00:17:29,910
We want to return true.

201
00:17:33,650 --> 00:17:41,360
Then this part and this next part, what we're going to do is decide whether to go left or right.

202
00:17:42,350 --> 00:17:51,170
So this is kind of like a pre-order traversal that we're doing here.

203
00:17:51,800 --> 00:17:59,210
So we are going through and we are checking for our value here.

204
00:17:59,750 --> 00:18:11,600
And we're doing we're going to say if the value is less than the current node's data.

205
00:18:13,370 --> 00:18:24,170
In that case, we're going to return recursive call of node and it's left century.

206
00:18:25,750 --> 00:18:29,980
So this whole sinister left some tree or else we're going to need to pass the value.

207
00:18:32,590 --> 00:18:37,210
Otherwise, if that's not the case, we don't even need for an else here because we have that return

208
00:18:37,210 --> 00:18:37,810
there already.

209
00:18:37,820 --> 00:18:40,390
So I'm just going to say return find.

210
00:18:40,390 --> 00:18:48,220
And the other case will be that we take the opposite direction, which will be the right century and

211
00:18:48,220 --> 00:18:50,110
we'll pass the value as well there.

212
00:18:51,370 --> 00:18:56,830
So basically, we're just saying like if we found the value, just return true, we do need for the

213
00:18:56,830 --> 00:19:01,270
base case to check, to see if we're at a null pointer before there.

214
00:19:01,270 --> 00:19:02,620
And then afterwards.

215
00:19:02,890 --> 00:19:10,900
We are saying that if we didn't find the value and the node is not no like we haven't gone off the end

216
00:19:10,900 --> 00:19:18,130
of a leaf node and seen that the direction we went was now no in its return nil point.

217
00:19:18,640 --> 00:19:28,240
We will then just be going left or right based on the value when it's less than or greater than.

218
00:19:31,140 --> 00:19:38,820
OK, cool, so now that we have that function out of the way, I'm actually going to use that for the

219
00:19:38,820 --> 00:19:41,070
insert function here.

220
00:19:41,640 --> 00:19:46,860
So we're just going to be calling find here.

221
00:19:47,520 --> 00:19:55,170
So I will say if we don't find this value in there already, and the reason I'm doing this is really

222
00:19:55,200 --> 00:20:04,170
just because I know that I said that it could be less than or equal to when we were doing the tree as

223
00:20:04,170 --> 00:20:10,350
far as like if we were to turn left or right, you know, would be like greater than.

224
00:20:13,250 --> 00:20:20,000
But what I'm going to do here is I'm just going to have it not put the similar similar values like we

225
00:20:20,000 --> 00:20:21,050
already have a value on that to you.

226
00:20:21,050 --> 00:20:25,640
We're not going to like put another value in there of the same, you know, the same value.

227
00:20:26,600 --> 00:20:28,400
So that's why I'm going to use this find.

228
00:20:28,400 --> 00:20:44,240
So I'm going to say if we don't find that value, then I'm going to say root equals insert root value.

229
00:20:49,410 --> 00:20:52,830
And then I'm going to do my actual implementation.

230
00:20:53,280 --> 00:21:00,270
The non client, Colleen won, so I will miss returns a pointer I'm going to say yes to.

231
00:21:01,200 --> 00:21:03,180
And search, and we want this one.

232
00:21:05,890 --> 00:21:15,970
So for the insertion, my base case is going to be if node equals null pointer again and then I'm going

233
00:21:15,970 --> 00:21:21,460
to say return new tree node.

234
00:21:21,670 --> 00:21:26,440
And this is why I have that other constructor there for the value because I'm going to create a new

235
00:21:26,440 --> 00:21:28,990
node that has the value that were passed into it.

236
00:21:33,390 --> 00:21:42,010
And so that would be inserting that here, and, you know, if we were to turn back back to here and

237
00:21:42,030 --> 00:21:54,300
we're saying equal to that, so I'm going to say if no data is less than three, then we're going to

238
00:21:54,300 --> 00:21:55,620
say that

239
00:21:58,500 --> 00:22:01,650
nodes right cemetery.

240
00:22:03,660 --> 00:22:05,430
And here it's going to be.

241
00:22:07,210 --> 00:22:12,070
Nodes are actually it when I'm going to do is I'm going to say insert.

242
00:22:15,480 --> 00:22:19,310
No race actually died.

243
00:22:24,260 --> 00:22:26,720
And then otherwise.

244
00:22:27,760 --> 00:22:29,380
I'm going to say.

245
00:22:32,960 --> 00:22:35,330
No less surgery.

246
00:22:36,590 --> 00:22:44,000
And then I'm going to call insert no less surgery value.

247
00:22:47,360 --> 00:22:52,690
And then down here, I'm just going to say we turn no.

248
00:22:56,370 --> 00:23:02,890
OK, so that should be all set up if you can look through this function here.

249
00:23:02,910 --> 00:23:06,990
Think back when to when we have the lecture and we were talking about inserting.

250
00:23:09,670 --> 00:23:18,250
If we're at a null pointer, that means that it's basically at a leaf node and we are ready to insert

251
00:23:18,250 --> 00:23:20,050
a new node to the tree there.

252
00:23:21,920 --> 00:23:32,300
Otherwise, we're saying if the node data, which is like Root, it were to seen originally, if that's

253
00:23:32,300 --> 00:23:40,820
less than the value that was passed, we are going to say that this node race tree is going to be set

254
00:23:40,820 --> 00:23:52,430
to a recursive call of the rice tree and the value so that kind of like trickles down and sets everything

255
00:23:52,520 --> 00:23:53,990
accordingly there.

256
00:23:54,530 --> 00:24:01,550
So that's why we put the recursive call in here because we're wanting to set it to potentially the a

257
00:24:01,550 --> 00:24:03,980
new node that we are creating right here.

258
00:24:05,070 --> 00:24:09,090
And then we have the opposite case for.

259
00:24:11,290 --> 00:24:16,030
We have the opposite case here where we're going down the list of, gee, I think I said this was the

260
00:24:16,120 --> 00:24:21,280
loss of Gee by accident, I might have said that, but we're doing the right cemetery first because

261
00:24:21,280 --> 00:24:28,690
we're seeing if the nodes data is less than the value as the current node we're at, and that would

262
00:24:28,690 --> 00:24:30,130
mean the value was greater.

263
00:24:30,160 --> 00:24:33,620
That's why we were doing the right century in an otherwise celestial tree.

264
00:24:33,640 --> 00:24:39,460
So sorry, if I mixed those up for you right there and then we're turning the node down here just to

265
00:24:39,460 --> 00:24:40,120
finish that off.

266
00:24:41,380 --> 00:24:46,780
OK, so we did the client version and our private version.

267
00:24:48,140 --> 00:24:49,100
Of this insert.

268
00:24:49,760 --> 00:24:53,300
So let's see what else do we have to do?

269
00:24:54,260 --> 00:24:58,850
We have the size and the in order.

270
00:25:00,200 --> 00:25:04,100
So let's go ahead and do that.

271
00:25:04,110 --> 00:25:06,170
Let's do the size, actually.

272
00:25:07,990 --> 00:25:15,950
So I'm going to do science right here, I say, and BSG sighs.

273
00:25:15,970 --> 00:25:24,430
We are doing the client version right now, so I'm going to say underscore size, which is our data

274
00:25:24,430 --> 00:25:35,110
member, and I'm going to say call this function that passes the root and then return size to the user.

275
00:25:38,180 --> 00:25:41,420
OK, let's make the other right inversion now.

276
00:25:42,350 --> 00:25:50,270
So this is going to be science with the Trino node similar to the ones.

277
00:25:51,860 --> 00:26:03,790
And then so I'm going to say, if node equals no point here, then return zero.

278
00:26:03,800 --> 00:26:08,530
So you want to think about the case in which there is nothing in the tree.

279
00:26:08,540 --> 00:26:14,810
So if it's just all initially, if Root is just null pointer, then we want to say that the size is

280
00:26:14,810 --> 00:26:15,170
zero.

281
00:26:15,170 --> 00:26:17,150
So that's why we're putting that as our base case.

282
00:26:19,890 --> 00:26:26,310
Otherwise, what we are going to do is kind of an interesting recursive call that you may not have thought

283
00:26:26,310 --> 00:26:26,850
about yet.

284
00:26:27,150 --> 00:26:33,030
We are going to return and remember our return value as an ant, and we're going to kind of sum up the

285
00:26:33,030 --> 00:26:33,660
nodes here.

286
00:26:33,660 --> 00:26:35,220
So I'm going to say one.

287
00:26:37,360 --> 00:26:45,190
Plus, the size of the current nodes, right century,

288
00:26:48,160 --> 00:27:00,910
plus the size of the current nodes left Sochi, and so what this does is basically for each time that

289
00:27:00,910 --> 00:27:05,380
we're coming through here and doing this recursive call, it's returning one.

290
00:27:05,380 --> 00:27:12,310
It's adding one for all the nodes in the in any given knows right of and any given nodes left some tree

291
00:27:12,730 --> 00:27:17,920
so you can think you we're using the integer one each time to represent each of the nodes that we would

292
00:27:17,920 --> 00:27:19,000
have to see visually there.

293
00:27:19,000 --> 00:27:24,940
And it's just basically talent in on another one every time it gets to a new node.

294
00:27:25,270 --> 00:27:28,940
So that's how this size function is working with this recursive call here.

295
00:27:29,500 --> 00:27:31,840
So kind of cool something new.

296
00:27:31,840 --> 00:27:36,460
We're adding recursive calls together with an integer as well.

297
00:27:38,750 --> 00:27:41,070
OK, so we have that out of the way.

298
00:27:41,090 --> 00:27:49,340
Now let's go ahead and just do our in order traversal one, which is in order to dump.

299
00:27:51,680 --> 00:27:57,080
So we're going to say boy GST in order dump.

300
00:27:58,010 --> 00:28:04,970
And I'm just going to do the client one first, which all it really does is just call this other in

301
00:28:04,970 --> 00:28:05,290
order.

302
00:28:07,430 --> 00:28:10,160
And this one has two parts to it.

303
00:28:13,890 --> 00:28:21,600
Now we're going to do our actual one that has most of the implementation testing route.

304
00:28:22,530 --> 00:28:24,920
So we're going to do our base case.

305
00:28:24,930 --> 00:28:27,240
It's going to be can you guess it?

306
00:28:27,240 --> 00:28:33,600
The same thing, if known, is no point area since the voice function, we're just going to return.

307
00:28:35,700 --> 00:28:39,220
And then what we're going to do, you probably know this already.

308
00:28:39,240 --> 00:28:42,740
See if you can figure out yourself kind of our.

309
00:28:43,890 --> 00:28:48,300
Got you a little close there, but see if you can pause the video and kind of guess what we're going

310
00:28:48,300 --> 00:28:53,310
to do before I go ahead and cut it, because you're pretty familiar with this after the likes you.

311
00:28:54,990 --> 00:29:03,600
OK, so what we're going to do is do in order dump, and then we will go to the left sub tree.

312
00:29:06,680 --> 00:29:09,680
And then we're going to print it out in the middle

313
00:29:13,190 --> 00:29:22,460
and damaged in line, and then we are going to do our in order dump of the right century.

314
00:29:25,700 --> 00:29:29,000
OK, so that one should have been actually easy for you after the lecture.

315
00:29:29,090 --> 00:29:31,520
It's pretty much the same exact thing that we saw there.

316
00:29:33,880 --> 00:29:34,150
All right.

317
00:29:34,240 --> 00:29:39,430
So now we kind of have all the functions I want to do right now, I don't I'm not going to do I don't

318
00:29:39,430 --> 00:29:44,950
think I'm going to do the iterative find is that the other one we have?

319
00:29:44,950 --> 00:29:45,850
Yeah, enter find.

320
00:29:46,180 --> 00:29:51,970
I'm going to have another section, I think, where we go over iterative functions.

321
00:29:52,180 --> 00:29:57,220
Well, we'll revisit this binary search tree and go over some iterative solutions to things.

322
00:29:57,940 --> 00:30:03,820
A lot of them have to do with a different data structure that we haven't gone over yet.

323
00:30:03,820 --> 00:30:11,260
And that's why ED Find would not have to use this new data structure I'm talking about, but a lot of

324
00:30:11,260 --> 00:30:12,820
the other iterative ones do.

325
00:30:13,660 --> 00:30:19,150
So what I'm going to do is wait until we discuss that data structure, and then we might just go ahead

326
00:30:19,150 --> 00:30:22,570
and revisit the binary search tree and try and make use of that.

327
00:30:24,130 --> 00:30:28,950
It's another data structure, and you just help us solve these recursive non recursive problems.

328
00:30:28,960 --> 00:30:34,900
Iterative ones with the loops when we're trying to do another version and non recursive version of a

329
00:30:34,900 --> 00:30:37,750
function or algorithm for a binary search tree.

330
00:30:38,200 --> 00:30:41,800
Let's go ahead and do the main file now.

331
00:30:42,220 --> 00:30:44,410
So I'm going to go over to main right now.

332
00:30:46,830 --> 00:30:55,180
Going to get rid of this, and we already have a stream there, I'm going to make a file actually,

333
00:30:55,180 --> 00:31:01,150
that we're going to use like a file stream object to take in our values to insert into the tree.

334
00:31:01,960 --> 00:31:03,370
So include a stream.

335
00:31:04,120 --> 00:31:07,720
And then of course, we want to include our header.

336
00:31:07,750 --> 00:31:10,630
So I'm going to do that each.

337
00:31:11,020 --> 00:31:16,840
And also this is trino dot h.

338
00:31:17,960 --> 00:31:18,260
OK.

339
00:31:18,430 --> 00:31:20,920
And do you sing in space?

340
00:31:22,270 --> 00:31:28,810
Let's go ahead and put this in here, since we're taking it from a file again to our NRC for the number

341
00:31:28,810 --> 00:31:34,570
of hours and then our charge star R&B array for arguments.

342
00:31:36,990 --> 00:31:38,430
I'm going to do a little check here.

343
00:31:39,030 --> 00:31:43,860
You know, like I can do this all the time to make sure that there is an argument being passed

344
00:31:47,040 --> 00:31:50,490
to the file and you're running it.

345
00:31:52,350 --> 00:32:01,470
So, you know, you put a little like a little usage error here to make sure the name of an input file.

346
00:32:06,290 --> 00:32:06,640
OK.

347
00:32:08,450 --> 00:32:14,660
And then you actually put these in brackets because I just want to say it with the FedEx Code after

348
00:32:14,660 --> 00:32:18,740
this, so actually just going to do that.

349
00:32:21,140 --> 00:32:23,360
OK, let's make an input file stream.

350
00:32:23,810 --> 00:32:31,700
You can call it file in your file and open and whatever was passed as a command line argument.

351
00:32:33,500 --> 00:32:36,080
And I'll make a new tree here.

352
00:32:36,200 --> 00:32:38,480
I'm just going to call it tree.

353
00:32:40,040 --> 00:32:50,060
And we'll say this new PSG, so that's just the default constructor, there are two integers so we can

354
00:32:50,840 --> 00:32:59,420
go ahead and read in from the file and insert them right here and say, let's insert into the tree.

355
00:33:00,500 --> 00:33:08,450
So while file in into our integer, I'm just going to say tree.

356
00:33:10,060 --> 00:33:15,680
Actually, I don't know if I would do anything else in around with the brackets anyways, say tree insert.

357
00:33:15,830 --> 00:33:18,350
And then I'm going to put three there.

358
00:33:18,920 --> 00:33:23,810
So we'll just loop through and insert all the values from our file into our binary search tree.

359
00:33:24,920 --> 00:33:25,310
OK.

360
00:33:25,340 --> 00:33:29,780
Next time around and go ahead and just call all my functions to make sure that they work, let's do

361
00:33:29,780 --> 00:33:30,050
them.

362
00:33:32,370 --> 00:33:40,650
In order, though, what's the first thing we should do is make sure that our tree actually got all

363
00:33:40,650 --> 00:33:46,920
the values inserted correctly and looks correct, so let's go ahead and do that in order to see if it

364
00:33:46,920 --> 00:33:49,230
prints them in the correct orders.

365
00:33:49,470 --> 00:33:52,080
That way, we know that our data structure is going to go.

366
00:33:52,620 --> 00:34:04,950
So I'm going to say we're going to see out in order jump out of the tree and to allow cannot type today.

367
00:34:06,480 --> 00:34:11,040
And then we will do Tree Arrows pointer in order downtown.

368
00:34:12,450 --> 00:34:16,000
So that will be proof that we got our values in.

369
00:34:16,020 --> 00:34:18,930
Let's go ahead and make a new file then.

370
00:34:19,980 --> 00:34:27,390
When I say just new file, I'll just call this and put to you.

371
00:34:28,950 --> 00:34:31,070
Let's go ahead and just do.

372
00:34:32,610 --> 00:34:39,420
I don't know, one five eight three five.

373
00:34:39,870 --> 00:34:40,150
No.

374
00:34:40,470 --> 00:34:46,950
Yeah, five percent have repeated value, so we'll test that feature to make sure that the find was

375
00:34:46,950 --> 00:34:49,990
working and wasn't doing repeated values there.

376
00:34:50,820 --> 00:34:54,450
Uh, eleven and twenty three.

377
00:34:54,720 --> 00:34:55,530
Let's just do that.

378
00:34:56,550 --> 00:35:00,210
So it should print them out in order.

379
00:35:01,110 --> 00:35:07,380
If our tree is all going to go and correct, we should see these printed out in order.

380
00:35:07,380 --> 00:35:10,080
So it would be a way for us to confirm.

381
00:35:13,730 --> 00:35:20,990
So I am going to go ahead and edit my configurations.

382
00:35:22,310 --> 00:35:26,620
And let's do, in fact, 60.

383
00:35:27,920 --> 00:35:28,250
Ford.

384
00:35:29,220 --> 00:35:29,610
All right.

385
00:35:31,780 --> 00:35:32,710
Try this again.

386
00:35:34,090 --> 00:35:35,440
All right, there we go.

387
00:35:36,600 --> 00:35:42,750
So I just needed to add that in there in order dump of three two three five eight 11 twenty three,

388
00:35:42,750 --> 00:35:44,700
it looks like it printed in order.

389
00:35:45,360 --> 00:35:47,660
So we're good to go there.

390
00:35:47,670 --> 00:35:57,900
Sorry, I had to navigate through all my personal files there for a bit and just tried to actually find

391
00:35:57,900 --> 00:35:58,470
that directory.

392
00:35:58,470 --> 00:36:00,180
I guess it was because I didn't save it yet.

393
00:36:01,350 --> 00:36:02,940
So apologies for that.

394
00:36:03,990 --> 00:36:05,610
Get to see my messy.

395
00:36:08,330 --> 00:36:09,050
Storage.

396
00:36:10,250 --> 00:36:11,420
How have organized things?

397
00:36:12,800 --> 00:36:20,750
Let's go ahead and do the next one then, so we will say we know that our find must be working well

398
00:36:20,750 --> 00:36:24,770
with this go ahead and just like check that explicitly as well.

399
00:36:25,880 --> 00:36:29,090
So enter a value to be found.

400
00:36:32,090 --> 00:36:41,840
And I'm just going to say C into an EF four find, oh, I did not define that yet, actually.

401
00:36:41,990 --> 00:36:43,190
So let me do that.

402
00:36:46,260 --> 00:36:49,710
I need to make an integer, and then I will say if

403
00:36:52,230 --> 00:36:59,670
tree find of F for fun, I will say it F.

404
00:37:02,550 --> 00:37:07,760
And I'll just say found with curses.

405
00:37:09,800 --> 00:37:13,350
Fine, I'm going to say that just because we might be doing it or find later.

406
00:37:17,430 --> 00:37:23,010
OK, and then I'm also going to check my size, so I'm going to go ahead and say, I'm going to see

407
00:37:23,010 --> 00:37:25,950
out the trees.

408
00:37:25,980 --> 00:37:27,600
Size is.

409
00:37:28,890 --> 00:37:35,400
And then we will see out tree size.

410
00:37:39,000 --> 00:37:41,410
OK, so let's check this out as well.

411
00:37:41,430 --> 00:37:44,280
We'll get the same in order to dump and then we should.

412
00:37:46,200 --> 00:37:51,360
Get a it should ask us for a value to be found.

413
00:37:53,020 --> 00:37:58,180
And then we'll enter that value and see if it's in our tree and then we can run again into something

414
00:37:58,180 --> 00:38:05,740
else to kind of double check it and then we will get the tree size, which should be one two three four

415
00:38:05,740 --> 00:38:06,970
five six seven.

416
00:38:07,210 --> 00:38:09,490
So let's go ahead and run this.

417
00:38:12,600 --> 00:38:16,190
OK, so enter a value to be found, let's say.

418
00:38:17,890 --> 00:38:20,380
Yeah, we'll say Kate into.

419
00:38:21,690 --> 00:38:27,390
Eight was found with recursive finesse as the trees size the seven, which is correct, should probably

420
00:38:27,720 --> 00:38:29,040
put a little space there.

421
00:38:29,610 --> 00:38:34,720
So let's go ahead and run this again and see if it finds something that's not in our trees.

422
00:38:34,740 --> 00:38:37,500
I was going to say forty five, actually, let's see.

423
00:38:37,500 --> 00:38:39,930
Let's say for your sake for.

424
00:38:41,500 --> 00:38:43,570
So it didn't say the floor was found.

425
00:38:45,080 --> 00:38:47,360
So that's good and says the chief scientist.

426
00:38:47,460 --> 00:38:47,720
Seven.

427
00:38:48,620 --> 00:38:52,490
All right, so we went over some kind of basic functions there.

428
00:38:52,760 --> 00:38:57,110
Hopefully, there's recursive functions where easy enough for you to understand.

429
00:38:57,590 --> 00:39:06,230
We're going to have some separate videos in the next part of this section where we're going to go over

430
00:39:06,230 --> 00:39:08,330
some a little bit more difficult.

431
00:39:10,320 --> 00:39:14,040
Functions, and I'm going to step through this in a very detailed manner with you.

432
00:39:14,790 --> 00:39:22,020
I will also include an exercise for you to try out a new function that's like a little bit easier and

433
00:39:22,020 --> 00:39:28,920
then we'll just go over the hard ones kind of in a video and step through them carefully so we can see

434
00:39:28,920 --> 00:39:29,640
what they're doing.

435
00:39:30,480 --> 00:39:35,520
Hopefully, you enjoyed this video and I will see you in the next one.