1
00:00:00,690 --> 00:00:02,190
Hello, everyone, and welcome back.

2
00:00:02,820 --> 00:00:07,380
In this video, I'm going to show you how we will cut out the solution to what we just came up with

3
00:00:07,380 --> 00:00:08,540
in the last few videos.

4
00:00:08,910 --> 00:00:11,160
There's actually a lot of code to write in this section.

5
00:00:11,160 --> 00:00:17,070
So if you do get lost at any point, I want you to just open up your resources folder and you'll find

6
00:00:17,070 --> 00:00:19,500
the final coded version of the solution.

7
00:00:19,500 --> 00:00:23,130
So it's easier to follow along if you need the full solution to look at.

8
00:00:23,730 --> 00:00:28,800
Another thing I will note is that because as we identified there, so many sub problems that we want

9
00:00:28,800 --> 00:00:33,930
to solve, we're going to want to break up our solution into many reusable functions.

10
00:00:34,050 --> 00:00:36,900
Even if we don't reuse the functions, we just want to separate it.

11
00:00:36,900 --> 00:00:43,320
So it's easier for us to make sure that we're doing the right thing as we solve this problem and code

12
00:00:43,320 --> 00:00:43,680
it out.

13
00:00:44,040 --> 00:00:48,870
Because in our minds, we know the steps that we want to take based on the logical way we broke down

14
00:00:48,870 --> 00:00:49,530
the problem.

15
00:00:49,560 --> 00:00:53,680
We just want to make sure that we don't confuse ourselves as we're actually coding it out.

16
00:00:54,330 --> 00:00:58,410
So here we're going to step into our initial function where we receive the root.

17
00:00:58,410 --> 00:01:01,400
And at first we always want to consider our null case.

18
00:01:01,740 --> 00:01:07,110
So we're going to say that if the root value we receive is undefined or null, then we just want to

19
00:01:07,110 --> 00:01:08,430
return zero.

20
00:01:09,860 --> 00:01:16,040
The next thing that we want to do is we want to figure out the actual value for the upper portion of

21
00:01:16,040 --> 00:01:21,890
our binary tree, which we know must be full in order to get this value, we need to calculate the height

22
00:01:21,890 --> 00:01:23,760
first, the size of our tree.

23
00:01:24,200 --> 00:01:29,930
So here I'm just going to say that we are going to have this value called height and it's going to be

24
00:01:29,930 --> 00:01:35,780
received through this function that I call get tree height that I'm going to code after we have our

25
00:01:35,780 --> 00:01:40,880
solution, because right now we just want to focus on breaking our problem into it's some problems.

26
00:01:41,000 --> 00:01:42,960
And the first one is we want to get the height of the tree.

27
00:01:43,460 --> 00:01:46,700
So this function is going to solve that for us and it's just going to receive the root.

28
00:01:46,700 --> 00:01:49,610
And I will quote it after once I have the height.

29
00:01:49,820 --> 00:01:55,460
What I'm going to say is that I want to make sure that the height of the tree is greater than just the

30
00:01:55,460 --> 00:01:56,080
base level.

31
00:01:56,540 --> 00:02:00,200
So this height value is going to start from zero at level one.

32
00:02:00,410 --> 00:02:05,930
The reason for this, as we know, is because in order to calculate the number of nodes at each level,

33
00:02:06,110 --> 00:02:11,660
we're doing two to the exponent and the first level is two to the exponent, zero because two to the

34
00:02:11,660 --> 00:02:13,630
exponent zero gives us one.

35
00:02:14,090 --> 00:02:19,520
So to begin with, if we only have one value, which is the root and that's the size of the entire tree,

36
00:02:19,550 --> 00:02:21,770
then our height will be of size zero.

37
00:02:21,830 --> 00:02:25,910
So here I'm going to say if height is size zero, then just return.

38
00:02:26,120 --> 00:02:26,540
What?

39
00:02:27,020 --> 00:02:31,310
There's no reason to go through the rest of the code if it's only that large.

40
00:02:32,150 --> 00:02:38,570
Once we do this, we now need to calculate the actual value of the number of nodes at this portion of

41
00:02:38,600 --> 00:02:39,280
the binary tree.

42
00:02:39,590 --> 00:02:47,210
And as we know, this can be calculated using two to the maximum height and then subtracting one from

43
00:02:47,210 --> 00:02:47,400
that.

44
00:02:47,630 --> 00:02:49,130
So here we can just write this out.

45
00:02:49,130 --> 00:02:53,320
Two to the zero to to the one, two to the two and then two to the three.

46
00:02:53,780 --> 00:02:58,940
So our height value for this height should be three and then we're just going to do two to three minus

47
00:02:58,940 --> 00:02:59,180
one.

48
00:03:00,360 --> 00:03:03,570
So here I'm going to say that consed upper.

49
00:03:06,050 --> 00:03:14,510
Is equal to math power, which gives us access to exponents, and I'm just going to say to to the value

50
00:03:14,510 --> 00:03:20,300
of our height minus one, and this gives us our upper value, which will be eight.

51
00:03:20,300 --> 00:03:21,560
Minus one, which is seven.

52
00:03:22,560 --> 00:03:30,270
Once I have the upper count and I've understood the size of this, I now also know the size of this

53
00:03:30,270 --> 00:03:35,740
level, the maximum number of notes that could be down here because it's going to be two to the height.

54
00:03:36,630 --> 00:03:41,280
So what we want want to do is we want to figure out where is this rightmost node at this level?

55
00:03:41,280 --> 00:03:43,800
And to do this, we're going to use the binary search solution.

56
00:03:44,190 --> 00:03:48,390
Our binary search solution, however, is a modified version where we're just trying to find the very

57
00:03:48,390 --> 00:03:50,130
last node that exists.

58
00:03:50,430 --> 00:03:56,640
So here we've got to implement the basic foundation of our binary search and modify it as we go to begin

59
00:03:56,640 --> 00:03:57,030
off with.

60
00:03:57,030 --> 00:03:58,990
We need a left and a right value.

61
00:03:59,370 --> 00:04:05,040
So here we're going to assume that the values down here are going to be indexed and the way we index

62
00:04:05,040 --> 00:04:08,730
them is just going to be from zero to the maximum value minus one.

63
00:04:10,010 --> 00:04:15,680
So the left value here is going to start at zero because we're indexing from zero and then the right

64
00:04:15,680 --> 00:04:22,040
value is going to be equal to math power of two to the height minus one, which we already have as our

65
00:04:22,040 --> 00:04:22,620
upper count.

66
00:04:22,730 --> 00:04:25,060
So luckily for us, we've already calculated this.

67
00:04:25,070 --> 00:04:26,750
We don't need to calculate it again.

68
00:04:28,230 --> 00:04:33,060
So once we have our left and right values, we now perform the binary search and we're going to implement

69
00:04:33,060 --> 00:04:34,380
this using our while loop.

70
00:04:34,620 --> 00:04:38,680
But remember, here left is not going to be less than or equal to right.

71
00:04:38,850 --> 00:04:40,830
We're not trying to find when they both overlap.

72
00:04:41,220 --> 00:04:44,090
We just want to make sure that we're checking for the value that exists.

73
00:04:44,490 --> 00:04:47,400
So here we're just going to say, well, left is less than right.

74
00:04:48,090 --> 00:04:52,440
I want to get the index to find, which is going to be the middle of these two values.

75
00:04:52,770 --> 00:04:55,920
So here I want to say that let index to find.

76
00:04:57,850 --> 00:05:02,350
Which is, again, the index of the note that we're looking for to see if it exists and I'm going to

77
00:05:02,350 --> 00:05:04,420
call math that ceiling which rounds up.

78
00:05:05,340 --> 00:05:08,070
And I want to say that left plus right.

79
00:05:11,930 --> 00:05:18,800
Once I have the index defined that is going to be from this middle value right here, then I am going

80
00:05:18,800 --> 00:05:23,630
to perform the search from the top all the way down to that node to see if it exists or not.

81
00:05:24,260 --> 00:05:28,280
That code, I'm also going to say that is going to be a function I'm going to implement after.

82
00:05:28,280 --> 00:05:31,850
I'm going to assume that we have an existing solution that will check for that node.

83
00:05:32,300 --> 00:05:35,780
And here I'm just going to call that function node exists.

84
00:05:37,360 --> 00:05:42,190
If you remember, this is following the same process of how we broke down this problem logically when

85
00:05:42,190 --> 00:05:47,050
we solved to figure out how to get the actual node first before we actually even figured out to see

86
00:05:47,050 --> 00:05:50,950
if the node exists, we're going to assume that the solution exists here.

87
00:05:50,950 --> 00:05:56,170
This node exists, is going to just receive the index to find, which is the value that we're looking

88
00:05:56,170 --> 00:05:56,490
for.

89
00:05:56,950 --> 00:05:58,700
It's also going to get the height of the tree.

90
00:05:59,200 --> 00:06:02,590
The reason why we passed the height of the tree is the height of the tree as the number of steps we're

91
00:06:02,590 --> 00:06:03,070
going to take.

92
00:06:03,670 --> 00:06:06,160
And then we're also going to pass at the root node.

93
00:06:08,380 --> 00:06:15,010
Once we have this implemented, we're going to say that if the node exists, then I want to shift my

94
00:06:15,010 --> 00:06:24,400
left to be equal to the index defined because as you remember, we are rounding up right here because

95
00:06:24,400 --> 00:06:27,050
we're rounding up or saying that it's inclusive on the right side.

96
00:06:27,100 --> 00:06:31,900
So here, if we implement this, just the double check, we'll see that we'll have a left of zero and

97
00:06:31,900 --> 00:06:36,670
a right of seven seven plus zero seven seven divided two is three point five, three by five rounded

98
00:06:36,670 --> 00:06:39,230
up is four if these are indexed.

99
00:06:39,490 --> 00:06:43,570
So the value that we're looking for is this one.

100
00:06:44,670 --> 00:06:50,610
What we're going to do is we're going to come down the tree, see that it exists, and then now if we

101
00:06:50,610 --> 00:06:54,000
know this node exists, we know that all the notes, the left of it exist.

102
00:06:54,330 --> 00:06:57,060
But we don't know if this is the rightmost node at this level.

103
00:06:57,090 --> 00:06:59,120
We don't know if any of these nodes exist.

104
00:06:59,460 --> 00:07:04,680
So that means that we have to consider the fact that this node may be the rightmost node, but it's

105
00:07:04,680 --> 00:07:05,300
not guaranteed.

106
00:07:05,700 --> 00:07:10,860
But what we can say is we want to reduce our search space from here.

107
00:07:14,290 --> 00:07:20,500
So that's really what we're doing, so if we want it to be inclusive, then that's how we shift our

108
00:07:20,500 --> 00:07:21,320
left over.

109
00:07:21,370 --> 00:07:23,650
So now our left is going to be equal.

110
00:07:24,780 --> 00:07:27,480
To four, and then our binary search continues.

111
00:07:28,980 --> 00:07:35,610
If the note does not exist, though, then what we're going to do is we know that if we found some note,

112
00:07:35,610 --> 00:07:40,530
let's say instead it was five, if we saw that this note does not exist, then we know for sure this

113
00:07:40,530 --> 00:07:42,240
note can't possibly be the answer.

114
00:07:42,390 --> 00:07:48,810
And we can shift the rights equal to this index minus one, which is essentially reducing our search

115
00:07:48,810 --> 00:07:50,910
space to this instead.

116
00:07:53,860 --> 00:07:56,650
Five was the value that we were looking for, and it did not exist.

117
00:07:57,550 --> 00:08:03,490
So here we're just going to say that right is equal to index to find.

118
00:08:07,510 --> 00:08:13,990
And this is all we need for the actual binary search, so here we can close our while loop.

119
00:08:14,620 --> 00:08:16,080
I do want to make one quick note.

120
00:08:16,570 --> 00:08:20,050
What will happen when we perform our binary search on this exact level?

121
00:08:20,620 --> 00:08:26,260
What is going to happen is that our left is going to end up at four and our right is going to end up

122
00:08:26,260 --> 00:08:26,870
at five.

123
00:08:26,890 --> 00:08:29,100
This is going to be the last search that gets performed.

124
00:08:29,230 --> 00:08:31,800
So we're going to have a left of four and a right of five.

125
00:08:32,560 --> 00:08:37,360
When you do this calculation, it's going to be four plus five, which is nine divided by two, four

126
00:08:37,360 --> 00:08:37,930
point five.

127
00:08:37,930 --> 00:08:40,340
And because we're rounding up, it's going to give us five.

128
00:08:40,720 --> 00:08:47,980
So once it checks that five does not exist, it will then attempt to perform this right equals index

129
00:08:47,980 --> 00:08:49,090
to find minus one.

130
00:08:49,660 --> 00:08:58,960
But the moment that happens right and left, both now equal four because five minus one is for our check

131
00:08:58,960 --> 00:09:03,790
for our while Loop says that we're only performing this loop as long as left is less than right.

132
00:09:04,680 --> 00:09:12,390
If left and right are both equal to four at this point, left is going to be equal to the actual final

133
00:09:12,390 --> 00:09:14,930
note, right is also going to be equal to the final note.

134
00:09:15,120 --> 00:09:21,270
So whichever one you want to use as the actual pointer for the node in order to get the final value

135
00:09:21,270 --> 00:09:22,320
is up to you.

136
00:09:22,470 --> 00:09:25,440
I'm just going to use the left, but that's the logic around why that works.

137
00:09:26,310 --> 00:09:32,490
So here what's going to happen is that we have our pointer, our left pointer, which is going to tell

138
00:09:32,490 --> 00:09:37,720
us the index value as well as we also have the upper count.

139
00:09:37,740 --> 00:09:44,100
So by combining these two, we can get the total count of nodes inside of this tree so we can just return

140
00:09:44,370 --> 00:09:53,300
as the actual answer, our upper count plus the left index value.

141
00:09:53,550 --> 00:09:59,340
But remember, because we're indexed at zero, we want to add one because we need the actual count nodes.

142
00:10:00,580 --> 00:10:04,410
And that is going to be the code for the count nodes, part of our solution.

143
00:10:05,110 --> 00:10:10,000
As for getting the height, we have to still fill out these two functions that we write.

144
00:10:10,780 --> 00:10:15,910
The note exists as well as get free height and get tree height is going to start from this root node

145
00:10:15,910 --> 00:10:21,190
and just go left until it hits a point where the nodes next left value does not exist and we're just

146
00:10:21,190 --> 00:10:22,250
going to count it along the way.

147
00:10:22,960 --> 00:10:26,410
So here I'm just going to say that the function name was get tree height.

148
00:10:29,140 --> 00:10:30,310
And it receives.

149
00:10:34,390 --> 00:10:43,750
What I'm going to do is I'm just going to first initialize the height as a value of zero, and I want

150
00:10:43,750 --> 00:10:48,670
to say that while root dot left does not.

151
00:10:49,730 --> 00:10:50,900
Equal, no.

152
00:10:52,980 --> 00:10:55,740
Then I am going to increment the count.

153
00:10:57,740 --> 00:11:02,780
And then I'm also going to say that root is equal to root left.

154
00:11:06,350 --> 00:11:12,110
And then once this is done, I'm just going to return the growing and accumulated high value.

155
00:11:13,310 --> 00:11:19,190
Now, if you're curious if the route is the only value inside of the binary tree receive meaning that

156
00:11:19,190 --> 00:11:24,720
it's only one level height is going to be zero, left is going to be null, which means that this wallet

157
00:11:24,740 --> 00:11:27,080
will not run and we're just going to return zero.

158
00:11:27,110 --> 00:11:31,850
And that's why we do this conditional check here to make sure to see that if height is equal to zero,

159
00:11:31,850 --> 00:11:34,980
then we return one, because that's the only value in our binary tree.

160
00:11:35,750 --> 00:11:40,340
The next thing that we need to implement is node exists and this function.

161
00:11:41,680 --> 00:11:47,440
Is pretty similar to the binary tree method that we just implemented, so here I'm going to say node

162
00:11:47,440 --> 00:11:50,590
exists is equal to a function.

163
00:11:51,960 --> 00:11:55,650
And it's going to start by receiving the index to find.

164
00:11:57,080 --> 00:12:03,890
It's also going to receive the height of the tree and it's also going to receive the node to start with,

165
00:12:03,890 --> 00:12:05,120
which will be the root.

166
00:12:06,720 --> 00:12:12,980
From here, we need to initialize our left and right pointers, so left, of course, is equal to zero,

167
00:12:13,410 --> 00:12:13,840
right?

168
00:12:13,860 --> 00:12:19,040
We're going to have to recalculate, which is just going to be the same exponent method that we had

169
00:12:19,500 --> 00:12:23,190
so mapped up, how we're going to take to as our base.

170
00:12:23,460 --> 00:12:24,510
We're going to give it the height.

171
00:12:25,480 --> 00:12:29,230
But once again, because we're indexing from zero, we've got to subtract one.

172
00:12:30,500 --> 00:12:35,150
And we're also going to initialize the count value, which is going to keep track of how many steps

173
00:12:35,150 --> 00:12:39,200
down that we've made, it starts from zero and it'll end when it reaches the height.

174
00:12:40,770 --> 00:12:46,350
And this is all of the variables we need now, we're going to perform our while loop and our while loop

175
00:12:46,350 --> 00:12:51,940
is based off of our count and we're going to increments it until it's equal to the height.

176
00:12:51,960 --> 00:12:58,050
So we're going to say that while the count is less than the height, we are going to now need the middle

177
00:12:58,050 --> 00:12:58,850
of the note.

178
00:12:59,640 --> 00:13:04,900
Now, the middle of the node is the exact same binary search method where we get the midpoint.

179
00:13:05,040 --> 00:13:10,740
But remember, from this node, the nodes it can access at this base level are from zero to seven.

180
00:13:11,370 --> 00:13:17,280
We want to get the middle of the node and then it's going to be rightside inclusive because we're rounding

181
00:13:17,280 --> 00:13:17,550
up.

182
00:13:17,940 --> 00:13:22,590
That means that if the node that we're looking for, which is the four, is equal to the middle of the

183
00:13:22,590 --> 00:13:24,400
node, which in our case happens to be four.

184
00:13:24,420 --> 00:13:25,680
So this proves the inclusiveness.

185
00:13:26,160 --> 00:13:31,050
If it's equal to or greater than four, then we know it falls on the right side.

186
00:13:31,380 --> 00:13:37,890
So if we're looking for four and we know that four is the start of our right side, then that's what

187
00:13:37,890 --> 00:13:41,550
we're representing with this variable called middle of node.

188
00:13:42,940 --> 00:13:51,010
So the middle of the node is equal to our math calculation, which is math dot seeling.

189
00:13:52,040 --> 00:13:54,620
Of the left plus the right.

190
00:13:58,190 --> 00:14:02,210
Now, we're just going to do this check and see that if the index to find.

191
00:14:04,900 --> 00:14:09,190
Is greater than or equal to our middle of Noad.

192
00:14:12,640 --> 00:14:15,160
Then we are going to traverse to the right.

193
00:14:16,170 --> 00:14:21,510
So we don't know yet if the note exists, we just know which side of our current note that we're looking

194
00:14:21,510 --> 00:14:24,910
at, that this note that we're looking for falls on.

195
00:14:25,410 --> 00:14:30,660
So if we know it falls on the right side, then we're going to say that the node is now equal to no

196
00:14:30,870 --> 00:14:31,140
right.

197
00:14:31,350 --> 00:14:33,890
Which is us taking one step down to the right.

198
00:14:34,680 --> 00:14:39,900
But now we have to shift our left over because we need to reduce the search space, because this new

199
00:14:39,900 --> 00:14:41,540
right side note does not have access.

200
00:14:41,560 --> 00:14:48,600
The entire bottom level, the only levels that has access to is from the middle of the node that we've

201
00:14:48,780 --> 00:14:52,430
mentioned is inclusive to what the right value is.

202
00:14:52,440 --> 00:14:53,630
So the right value stays the same.

203
00:14:55,580 --> 00:15:01,910
If this is not the case, then we are going to move left and said so we'll say that note is equal to

204
00:15:01,910 --> 00:15:03,530
node dot left.

205
00:15:05,740 --> 00:15:08,930
And then our right value is the one that now needs to shrink.

206
00:15:09,550 --> 00:15:14,140
So we're going to say that it's equal to mid of Noad, minus one.

207
00:15:19,100 --> 00:15:23,390
Once we've done this, we have our check in place, we're just going to increment the count because

208
00:15:23,390 --> 00:15:29,690
the count is what going to tell our code how many steps you've taken, because once you've taken enough

209
00:15:29,690 --> 00:15:35,080
steps, the node value is now going to be equal to the value that we want from here.

210
00:15:35,240 --> 00:15:36,680
We need to check if it exists.

211
00:15:36,680 --> 00:15:38,270
And that's what we're just going to return from.

212
00:15:38,270 --> 00:15:40,780
This function's function just checks if the note exists.

213
00:15:41,090 --> 00:15:44,450
So here you're just going to say no does not equal null.

214
00:15:46,020 --> 00:15:50,980
If the note does not equal no, it'll return true if the note is equal to null its return false.

215
00:15:51,000 --> 00:15:55,310
And that's how we implement if the note exists and this is our solution.

216
00:15:56,100 --> 00:16:01,650
So it's a lot of code we have to write, but it really just follows the exact same logical step through

217
00:16:01,830 --> 00:16:06,110
literally code by code, line by line that we came up with in the last few lessons.

218
00:16:06,630 --> 00:16:13,650
So as far as the space and time complexity goes, when we look at the actual count nodes itself, the

219
00:16:13,650 --> 00:16:20,970
portions here that are important is the get height, get free height here, runs in O of the depth so

220
00:16:20,970 --> 00:16:27,960
we can say it's O of H, which is the height sorry, not the depth of H, which in our case we know

221
00:16:27,960 --> 00:16:33,960
is O of log N but and here might vary depending on the size of the nodes.

222
00:16:34,140 --> 00:16:42,780
So if you do say log n just mentioned that N is the number of actual children or potential nodes inside

223
00:16:42,780 --> 00:16:44,250
of this full complete tree.

224
00:16:44,670 --> 00:16:48,960
But if they're a stickler you can say H h represents the height of the tree.

225
00:16:50,000 --> 00:16:52,280
That is what the get height is.

226
00:16:53,260 --> 00:17:01,240
As far as the actual upper count's calculation, this is O of one, the actual while loop here, the

227
00:17:01,240 --> 00:17:09,190
number of times this is going to run is going to be o of log of and over two, because there's an over

228
00:17:09,190 --> 00:17:12,610
two nodes down here or potential nodes that we can scan through.

229
00:17:13,240 --> 00:17:16,770
And as we know, binary search cuts it in half and throws it away.

230
00:17:16,930 --> 00:17:19,780
So it's log of and over to.

231
00:17:21,230 --> 00:17:27,680
And as we know, and over two is equal to and because we have to drop the consent of the two and log

232
00:17:27,680 --> 00:17:31,350
of N is equal to the height of the tree, which is still the H value.

233
00:17:31,790 --> 00:17:35,060
So here we can say that this while loop function performs.

234
00:17:36,420 --> 00:17:40,950
In O of H as well, you can say logon at this point as well.

235
00:17:40,980 --> 00:17:42,300
It's really up to you once again.

236
00:17:42,300 --> 00:17:45,480
It's all preference, but the last calculation is going to be in here.

237
00:17:45,630 --> 00:17:47,620
This note exists portion of the code.

238
00:17:48,060 --> 00:17:50,660
How many times are we calling node exists?

239
00:17:50,700 --> 00:17:57,960
We're calling it of H Times, because for every time we do this half check and throw away of our binary

240
00:17:57,960 --> 00:18:03,450
search here, we're performing a node exists check, which goes from the root all the way down as we

241
00:18:03,450 --> 00:18:05,400
know this goes H steps as well.

242
00:18:05,430 --> 00:18:12,720
So this is also O of H, which is the node exists function time, which means that the overall runtime

243
00:18:12,720 --> 00:18:16,900
of this binary search within binary search is O of H squared.

244
00:18:17,430 --> 00:18:25,020
So this means that the time complexity of the function as a whole is big O of H squared plus H the H

245
00:18:25,020 --> 00:18:26,010
coming from up here.

246
00:18:26,490 --> 00:18:29,930
Of course we can drop this H because it's smaller than H squared.

247
00:18:30,120 --> 00:18:32,490
So our actual time is of H squared.

248
00:18:32,790 --> 00:18:39,870
If instead of H squared you want to use the log and notation, this is going to be log of N multiplied

249
00:18:39,870 --> 00:18:44,550
by log of N which is equal to log squared.

250
00:18:44,560 --> 00:18:48,030
And this is not the same as log and squared.

251
00:18:48,150 --> 00:18:49,730
These are two completely different things.

252
00:18:49,740 --> 00:18:50,460
You have to remember.

253
00:18:50,460 --> 00:18:54,600
We're not actually multiplying the ends and then getting the log value of squared.

254
00:18:54,870 --> 00:18:59,700
We're saying it's log N times log N, which is what this syntax represents.

255
00:18:59,910 --> 00:19:03,330
So just remember that if you do choose to use the log and notation.

256
00:19:04,970 --> 00:19:10,670
Now that we understand this, we have our time, complexity, we also need our space complexity space

257
00:19:10,670 --> 00:19:12,350
here, we're writing it out of code.

258
00:19:12,350 --> 00:19:14,750
It's while loops, there's no scaling data structures.

259
00:19:14,780 --> 00:19:17,020
So we're actually achieved an O of one.

260
00:19:17,570 --> 00:19:22,610
And here we've managed to achieve a time complexity that is better than zero of NP.

261
00:19:23,270 --> 00:19:29,960
And we it's much more complicated and it's going to be difficult to do inside of your actual interview.

262
00:19:30,320 --> 00:19:35,570
But the key is that you want to walk through these steps and just demonstrate that you are making all

263
00:19:35,570 --> 00:19:41,740
of the correct insights and you're thinking about the problem in a meaningful way and breaking it apart.

264
00:19:41,930 --> 00:19:48,080
That's really part of why this is such a good problem, because it really shows and can demonstrate

265
00:19:48,080 --> 00:19:54,350
to your interviewer how good you are at breaking up the problem into the correct sub problems and then

266
00:19:54,350 --> 00:19:56,240
figuring out how to tackle those pieces.

267
00:19:56,510 --> 00:20:00,860
Even if you don't put it all together or even if you don't manage to code at all, you're really just

268
00:20:00,860 --> 00:20:05,480
demonstrating that you understand how to walk through and break the problem down and communicate that

269
00:20:05,480 --> 00:20:09,890
effectively to your interviewer, which is really what they are testing you for.

270
00:20:10,790 --> 00:20:17,000
So this wraps up our section on complete and full trees once again, if you get either of these trees,

271
00:20:17,000 --> 00:20:22,130
really think about the question and what it might imply, because they're giving you this specific type

272
00:20:22,130 --> 00:20:22,610
of tree.

273
00:20:23,060 --> 00:20:25,370
Maybe it's combined with traversal, maybe it's not.

274
00:20:25,490 --> 00:20:31,910
The trick is really just a step back and break this problem down bit by bit by bit and communicate and

275
00:20:31,910 --> 00:20:34,950
try and figure out what the problem actually wants you to do.

276
00:20:35,510 --> 00:20:38,180
So let's move on to binary search trees.