Hello, everyone, and welcome back.
In this video, I'm going to show you how we will cut out the solution to what we just came up with
in the last few videos.
There's actually a lot of code to write in this section.
So if you do get lost at any point, I want you to just open up your resources folder and you'll find
the final coded version of the solution.
So it's easier to follow along if you need the full solution to look at.
Another thing I will note is that because as we identified there, so many sub problems that we want
to solve, we're going to want to break up our solution into many reusable functions.
Even if we don't reuse the functions, we just want to separate it.
So it's easier for us to make sure that we're doing the right thing as we solve this problem and code
it out.
Because in our minds, we know the steps that we want to take based on the logical way we broke down
the problem.
We just want to make sure that we don't confuse ourselves as we're actually coding it out.
So here we're going to step into our initial function where we receive the root.
And at first we always want to consider our null case.
So we're going to say that if the root value we receive is undefined or null, then we just want to
return zero.
The next thing that we want to do is we want to figure out the actual value for the upper portion of
our binary tree, which we know must be full in order to get this value, we need to calculate the height
first, the size of our tree.
So here I'm just going to say that we are going to have this value called height and it's going to be
received through this function that I call get tree height that I'm going to code after we have our
solution, because right now we just want to focus on breaking our problem into it's some problems.
And the first one is we want to get the height of the tree.
So this function is going to solve that for us and it's just going to receive the root.
And I will quote it after once I have the height.
What I'm going to say is that I want to make sure that the height of the tree is greater than just the
base level.
So this height value is going to start from zero at level one.
The reason for this, as we know, is because in order to calculate the number of nodes at each level,
we're doing two to the exponent and the first level is two to the exponent, zero because two to the
exponent zero gives us one.
So to begin with, if we only have one value, which is the root and that's the size of the entire tree,
then our height will be of size zero.
So here I'm going to say if height is size zero, then just return.
What?
There's no reason to go through the rest of the code if it's only that large.
Once we do this, we now need to calculate the actual value of the number of nodes at this portion of
the binary tree.
And as we know, this can be calculated using two to the maximum height and then subtracting one from
that.
So here we can just write this out.
Two to the zero to to the one, two to the two and then two to the three.
So our height value for this height should be three and then we're just going to do two to three minus
one.
So here I'm going to say that consed upper.
Is equal to math power, which gives us access to exponents, and I'm just going to say to to the value
of our height minus one, and this gives us our upper value, which will be eight.
Minus one, which is seven.
Once I have the upper count and I've understood the size of this, I now also know the size of this
level, the maximum number of notes that could be down here because it's going to be two to the height.
So what we want want to do is we want to figure out where is this rightmost node at this level?
And to do this, we're going to use the binary search solution.
Our binary search solution, however, is a modified version where we're just trying to find the very
last node that exists.
So here we've got to implement the basic foundation of our binary search and modify it as we go to begin
off with.
We need a left and a right value.
So here we're going to assume that the values down here are going to be indexed and the way we index
them is just going to be from zero to the maximum value minus one.
So the left value here is going to start at zero because we're indexing from zero and then the right
value is going to be equal to math power of two to the height minus one, which we already have as our
upper count.
So luckily for us, we've already calculated this.
We don't need to calculate it again.
So once we have our left and right values, we now perform the binary search and we're going to implement
this using our while loop.
But remember, here left is not going to be less than or equal to right.
We're not trying to find when they both overlap.
We just want to make sure that we're checking for the value that exists.
So here we're just going to say, well, left is less than right.
I want to get the index to find, which is going to be the middle of these two values.
So here I want to say that let index to find.
Which is, again, the index of the note that we're looking for to see if it exists and I'm going to
call math that ceiling which rounds up.
And I want to say that left plus right.
Once I have the index defined that is going to be from this middle value right here, then I am going
to perform the search from the top all the way down to that node to see if it exists or not.
That code, I'm also going to say that is going to be a function I'm going to implement after.
I'm going to assume that we have an existing solution that will check for that node.
And here I'm just going to call that function node exists.
If you remember, this is following the same process of how we broke down this problem logically when
we solved to figure out how to get the actual node first before we actually even figured out to see
if the node exists, we're going to assume that the solution exists here.
This node exists, is going to just receive the index to find, which is the value that we're looking
for.
It's also going to get the height of the tree.
The reason why we passed the height of the tree is the height of the tree as the number of steps we're
going to take.
And then we're also going to pass at the root node.
Once we have this implemented, we're going to say that if the node exists, then I want to shift my
left to be equal to the index defined because as you remember, we are rounding up right here because
we're rounding up or saying that it's inclusive on the right side.
So here, if we implement this, just the double check, we'll see that we'll have a left of zero and
a right of seven seven plus zero seven seven divided two is three point five, three by five rounded
up is four if these are indexed.
So the value that we're looking for is this one.
What we're going to do is we're going to come down the tree, see that it exists, and then now if we
know this node exists, we know that all the notes, the left of it exist.
But we don't know if this is the rightmost node at this level.
We don't know if any of these nodes exist.
So that means that we have to consider the fact that this node may be the rightmost node, but it's
not guaranteed.
But what we can say is we want to reduce our search space from here.
So that's really what we're doing, so if we want it to be inclusive, then that's how we shift our
left over.
So now our left is going to be equal.
To four, and then our binary search continues.
If the note does not exist, though, then what we're going to do is we know that if we found some note,
let's say instead it was five, if we saw that this note does not exist, then we know for sure this
note can't possibly be the answer.
And we can shift the rights equal to this index minus one, which is essentially reducing our search
space to this instead.
Five was the value that we were looking for, and it did not exist.
So here we're just going to say that right is equal to index to find.
And this is all we need for the actual binary search, so here we can close our while loop.
I do want to make one quick note.
What will happen when we perform our binary search on this exact level?
What is going to happen is that our left is going to end up at four and our right is going to end up
at five.
This is going to be the last search that gets performed.
So we're going to have a left of four and a right of five.
When you do this calculation, it's going to be four plus five, which is nine divided by two, four
point five.
And because we're rounding up, it's going to give us five.
So once it checks that five does not exist, it will then attempt to perform this right equals index
to find minus one.
But the moment that happens right and left, both now equal four because five minus one is for our check
for our while Loop says that we're only performing this loop as long as left is less than right.
If left and right are both equal to four at this point, left is going to be equal to the actual final
note, right is also going to be equal to the final note.
So whichever one you want to use as the actual pointer for the node in order to get the final value
is up to you.
I'm just going to use the left, but that's the logic around why that works.
So here what's going to happen is that we have our pointer, our left pointer, which is going to tell
us the index value as well as we also have the upper count.
So by combining these two, we can get the total count of nodes inside of this tree so we can just return
as the actual answer, our upper count plus the left index value.
But remember, because we're indexed at zero, we want to add one because we need the actual count nodes.
And that is going to be the code for the count nodes, part of our solution.
As for getting the height, we have to still fill out these two functions that we write.
The note exists as well as get free height and get tree height is going to start from this root node
and just go left until it hits a point where the nodes next left value does not exist and we're just
going to count it along the way.
So here I'm just going to say that the function name was get tree height.
And it receives.
What I'm going to do is I'm just going to first initialize the height as a value of zero, and I want
to say that while root dot left does not.
Equal, no.
Then I am going to increment the count.
And then I'm also going to say that root is equal to root left.
And then once this is done, I'm just going to return the growing and accumulated high value.
Now, if you're curious if the route is the only value inside of the binary tree receive meaning that
it's only one level height is going to be zero, left is going to be null, which means that this wallet
will not run and we're just going to return zero.
And that's why we do this conditional check here to make sure to see that if height is equal to zero,
then we return one, because that's the only value in our binary tree.
The next thing that we need to implement is node exists and this function.
Is pretty similar to the binary tree method that we just implemented, so here I'm going to say node
exists is equal to a function.
And it's going to start by receiving the index to find.
It's also going to receive the height of the tree and it's also going to receive the node to start with,
which will be the root.
From here, we need to initialize our left and right pointers, so left, of course, is equal to zero,
right?
We're going to have to recalculate, which is just going to be the same exponent method that we had
so mapped up, how we're going to take to as our base.
We're going to give it the height.
But once again, because we're indexing from zero, we've got to subtract one.
And we're also going to initialize the count value, which is going to keep track of how many steps
down that we've made, it starts from zero and it'll end when it reaches the height.
And this is all of the variables we need now, we're going to perform our while loop and our while loop
is based off of our count and we're going to increments it until it's equal to the height.
So we're going to say that while the count is less than the height, we are going to now need the middle
of the note.
Now, the middle of the node is the exact same binary search method where we get the midpoint.
But remember, from this node, the nodes it can access at this base level are from zero to seven.
We want to get the middle of the node and then it's going to be rightside inclusive because we're rounding
up.
That means that if the node that we're looking for, which is the four, is equal to the middle of the
node, which in our case happens to be four.
So this proves the inclusiveness.
If it's equal to or greater than four, then we know it falls on the right side.
So if we're looking for four and we know that four is the start of our right side, then that's what
we're representing with this variable called middle of node.
So the middle of the node is equal to our math calculation, which is math dot seeling.
Of the left plus the right.
Now, we're just going to do this check and see that if the index to find.
Is greater than or equal to our middle of Noad.
Then we are going to traverse to the right.
So we don't know yet if the note exists, we just know which side of our current note that we're looking
at, that this note that we're looking for falls on.
So if we know it falls on the right side, then we're going to say that the node is now equal to no
right.
Which is us taking one step down to the right.
But now we have to shift our left over because we need to reduce the search space, because this new
right side note does not have access.
The entire bottom level, the only levels that has access to is from the middle of the node that we've
mentioned is inclusive to what the right value is.
So the right value stays the same.
If this is not the case, then we are going to move left and said so we'll say that note is equal to
node dot left.
And then our right value is the one that now needs to shrink.
So we're going to say that it's equal to mid of Noad, minus one.
Once we've done this, we have our check in place, we're just going to increment the count because
the count is what going to tell our code how many steps you've taken, because once you've taken enough
steps, the node value is now going to be equal to the value that we want from here.
We need to check if it exists.
And that's what we're just going to return from.
This function's function just checks if the note exists.
So here you're just going to say no does not equal null.
If the note does not equal no, it'll return true if the note is equal to null its return false.
And that's how we implement if the note exists and this is our solution.
So it's a lot of code we have to write, but it really just follows the exact same logical step through
literally code by code, line by line that we came up with in the last few lessons.
So as far as the space and time complexity goes, when we look at the actual count nodes itself, the
portions here that are important is the get height, get free height here, runs in O of the depth so
we can say it's O of H, which is the height sorry, not the depth of H, which in our case we know
is O of log N but and here might vary depending on the size of the nodes.
So if you do say log n just mentioned that N is the number of actual children or potential nodes inside
of this full complete tree.
But if they're a stickler you can say H h represents the height of the tree.
That is what the get height is.
As far as the actual upper count's calculation, this is O of one, the actual while loop here, the
number of times this is going to run is going to be o of log of and over two, because there's an over
two nodes down here or potential nodes that we can scan through.
And as we know, binary search cuts it in half and throws it away.
So it's log of and over to.
And as we know, and over two is equal to and because we have to drop the consent of the two and log
of N is equal to the height of the tree, which is still the H value.
So here we can say that this while loop function performs.
In O of H as well, you can say logon at this point as well.
It's really up to you once again.
It's all preference, but the last calculation is going to be in here.
This note exists portion of the code.
How many times are we calling node exists?
We're calling it of H Times, because for every time we do this half check and throw away of our binary
search here, we're performing a node exists check, which goes from the root all the way down as we
know this goes H steps as well.
So this is also O of H, which is the node exists function time, which means that the overall runtime
of this binary search within binary search is O of H squared.
So this means that the time complexity of the function as a whole is big O of H squared plus H the H
coming from up here.
Of course we can drop this H because it's smaller than H squared.
So our actual time is of H squared.
If instead of H squared you want to use the log and notation, this is going to be log of N multiplied
by log of N which is equal to log squared.
And this is not the same as log and squared.
These are two completely different things.
You have to remember.
We're not actually multiplying the ends and then getting the log value of squared.
We're saying it's log N times log N, which is what this syntax represents.
So just remember that if you do choose to use the log and notation.
Now that we understand this, we have our time, complexity, we also need our space complexity space
here, we're writing it out of code.
It's while loops, there's no scaling data structures.
So we're actually achieved an O of one.
And here we've managed to achieve a time complexity that is better than zero of NP.
And we it's much more complicated and it's going to be difficult to do inside of your actual interview.
But the key is that you want to walk through these steps and just demonstrate that you are making all
of the correct insights and you're thinking about the problem in a meaningful way and breaking it apart.
That's really part of why this is such a good problem, because it really shows and can demonstrate
to your interviewer how good you are at breaking up the problem into the correct sub problems and then
figuring out how to tackle those pieces.
Even if you don't put it all together or even if you don't manage to code at all, you're really just
demonstrating that you understand how to walk through and break the problem down and communicate that
effectively to your interviewer, which is really what they are testing you for.
So this wraps up our section on complete and full trees once again, if you get either of these trees,
really think about the question and what it might imply, because they're giving you this specific type
of tree.
Maybe it's combined with traversal, maybe it's not.
The trick is really just a step back and break this problem down bit by bit by bit and communicate and
try and figure out what the problem actually wants you to do.
So let's move on to binary search trees.