Welcome back, everyone.
Hopefully you got a chance to really think about this complete binary tree question, here is an example
where when I mentioned before, does the traversal matter and does it drive you towards breath for a
search and deeper search?
I said that ninety five percent of the time it does.
Five percent of the time it doesn't.
This question is a perfect example of one where it doesn't because it leverages more on our critical
and abstract thinking involving the complete binary tree structure than the actual traversal algorithms
that we've been practicing for the last few binary tree questions.
So to begin with, what we need to really think about is the fact that this is a complete tree and we
have to think about what characteristics are there as well as what goal we're trying to achieve.
In our particular case, we're trying to count the number of nodes in this tree.
So let's take the idea that we're looking for the total number of nodes in any given tree, but also
the fact that it's a complete tree.
What are the facts about complete trees?
Complete trees are full at every single level except for the last one.
So in a way, you can see that you almost have to break up this problem of counting the nodes in the
tree into two sections.
The first section is every level except for the very last level.
The second section is the very last level.
As we see in all of these three different binary trees we've drawn.
They are of the exact same height, but the only variability in the number of nodes lives in the last
level.
So if we break this problem into two sections, well, we're able to do is say how efficiently can I
count the number of nodes above this last level and then how efficiently can I count the number of nodes
in this last level.
So let's start with this first portion, which is every level of the nodes except for the last level.
We also want to keep in mind that for each of these sections, we're trying to achieve an optimal time
better than zero of NP because o of and is what we can achieve already with deeper search and breathless
search.
A more convoluted solution that still achieves O of end is not a more optimal solution, which means
that each of these sections must be able to be performed in either O of log N or O of one, because
these are the only two complexities that are more performant than O of end.
So knowing that, let's think about how can we calculate the size of this part of the tree.
If we look at this tree, we know that every single node at these levels that we're considering right
now must be completely full.
So what's the relationship and what's the best way we can get these values?
If we think about it, these values are always doubling.
And what we think about doubling and then doubling and then doubling, what we're saying is that we're
essentially achieving two to the exponent of some value in this case.
Let's use this intuition and figure out what the values are for this so that we can calculate the number
of notes here.
We have one node two to what gives us one two to the zero gives us one similarily, two to what gives
us two.
Well, two to one gives us two.
And then the next level is four two to the power to gives us for the next level.
We have eight two to the three gives us eight here.
I'm just showing you that this is two to the three will give us the eight value.
But once again we don't know if this level is completely full with a complete tree, but you can see
the relationship very clearly here.
If we were to count the number of nodes, we see that there's one, two, three, four, five, six,
seven nodes in this top half.
What we can also do is just add these values together, two to the zero, which is one, two to the
one, which is two, two to the two, which is four.
So one plus two plus four also gives us seven.
If we look at this relationship, though, we noticed that at this very last level, which is two to
the three, this gives us eight.
If we were to write out all of these values, we'd say that there's one here.
Let me just erase these so we're more clear here.
We have one at the first level, then two at the next level, then for the next level, then eight at
the next level, then we have 16 at the falling level because it's two to the four.
And similarly, the next level of two to the five, we double 16, which gives us thirty to.
Let's think about the relationship between this portion of the tree and this next level of values here.
We can see very clearly that if we had a tree of this size just up until this point.
The number of values in this portion of the tree is equal to three.
At the next level, it's equal to four, four minus one also gives us three similarily eight minus one
gives us seven, which is the same as the number of values that we are looking for right here in this
part of the tree.
We can imagine then that if we were to count the number of values in the whole tree, which is full,
it's one, two, three, four, five, six, seven, eight, nine, 10, 11, 12, 13, 14, 15, 15
is one less than the next level.
So what we can say is that the value of the number of nodes in this upper portion of the tree is equal
to two to the height of the tree, minus one and then minus one from that total value.
The reason why it's H minus one is because the height value is equal to for this tree is of height four.
But we are assuming that the base height is at two to the zero.
So we want to subtract one to get the number of nodes at this level, which is eight.
And then we want to subtract one from eight to get the total number of nodes here.
So that's why we got two to the minus one, minus one.
This mathematical calculation runs in O of one time, which is great.
But what about getting the actual height value?
What's the time it takes to get the height of the tree and what's the best way that we can do that?
Well, when we look at these three variations of our complete binary tree, we see that this tree is
the one that's the most limiting because it only has one value inside of its last level.
So if we were to use this as our worst case scenario to determine the height, the way that we would
do it is we would start from the very root node, which is the node that we receive in our function,
and we would traverse down depth first search all the way to the very bottom until we find a node where
the left next value is equal to null.
If we counted the number of steps that we took along the way, then we could easily get the height.
So if we initialize at zero, we get to the root node.
So we get one.
Then we go left.
It's two, then we go left, it's three.
Then we go left.
It's four.
And once we try and go left again, we see that the value is null.
So four is the actual height of our tree and now we've managed to get our value for H.
But what's the performance of doing this traversal here?
What we see is that we took four steps, which is the height of the tree.
So we can say that in any case, it runs end of time.
Now, what is the height of a complete binary tree?
We already know this.
This is log of N log base.
Two of the full number of nodes in this tree is equal to the height of the tree so long and gives us
the actual height.
So this means that this runtime for finding the height is O of log N.
If we combine it with the mathematical calculation then it's O of log N plus O of one of one is significantly
smaller.
So we drop it and log and becomes the time it takes for us to calculate the number of nodes in this
portion of any complete binary tree.
This portion is not limited to the binary tree of this size.
It's any complete binary tree.
This calculation is consistent.
So now that we understand how to get the number of nodes up here, we have to tackle getting the number
of nodes down here.
So I actually want you to try and figure out a way to get the number of nodes down at this last level
here.
I will give you a couple of hints.
You want to think about what it is that you want to find while keeping in mind the condition that for
all the nodes that could be in this level, they must all be pushed to the very left, meaning that
if you are able to find the right most node at this level, you can assume that all the notes the left
exist, which means that if you are able to figure out what number from left to right this node is,
you could immediately tell how many nodes are in this level.
The trick, though, is figuring out that this is the right note to look for, because once again,
we are starting from the context of this root node.
At this point, we have no idea how many nodes are down here, but we don't know the maximum number
of nodes that it could possibly be.
We also know that the minimum number of note that it could possibly be as well, so these bits of knowledge
combined might be able to help you figure it out.
I will give you another hint, which is the fact that you need to do this in a given time and you're
essentially searching for a note.
And I don't want you to be locked into the idea that you're searching in a binary tree structure, at
least for the idea what search can we perform in log and time?
We already know that the only search that can perform and log in time is binary search.
So how do we perform binary search on this structure to get this value?
That's my challenge to you.
You don't have to be able to do it right away.
I just want you to think about it and really fight with it to figure it out, because there's a lot
of steps here in order to get this to work with binary search.
But that's the big hint to you.
Not only do you have to determine the value that you're looking for, but you also have to determine
how to verify if that value exists from the route.
You need to combine those two things together in order to come up with an optimal solution that all
performs in log and time.
So that's my challenge to you.
Try and see if you can figure out at least parts of it, and I'll show you how we can do it in the next
video.