Welcome back, everyone.
Up until this point, we've only looked at normal binary trees.
Sometimes interviewers will like to throw in the complexity by mentioning that the tree is full and
or complete.
In this lesson, we're going to look at a question where the binary tree will be one of these types.
And we're going to analyze how that changes the insights that we can glean from this type of binary
tree.
So first, let's just quickly go over the differences between full and complete trees, a full tree
is one where every tree node has either zero children or two children.
That's the only stipulation.
This tree can be any level and not all levels can be completely full.
All that matters is that any tree node inside of this tree has either two children or no children.
A complete tree, on the other hand, is one where every level is completely full.
The only level that doesn't need to be fall is the last level.
And even if it's not, all of the nodes must be pushed as far left as possible, meaning that you could
end up with a tree, which in this case with this given structure, has three nodes at the bottom.
All push the left though, or two nodes or one node.
The trick is just that that last level, the nodes that are there must be as left as they can be.
A tree can also be full and complete.
In this case, every level is filled with nodes and here you can see it fulfills both the stipulations.
It is a full tree because every node has either two children or no children, and it is complete because
every level is completely filled, including the last level.
Generally speaking, there's more complexity and nuance to receiving a complete treat rather than a
full tree, and we're going to see why in this next question.
The question says that given a complete binary tree count, the number of nodes in the tree, we can
see that if we were given this binary tree structure, if we count the number of nodes here, we'll
end up with 15 nodes.
But because a complete binary tree doesn't necessarily have to have that bottom level completely full,
we could receive this binary tree, which has 12 nodes or this binary tree which has eight nodes.
When we begin to solve for this actual question, we have to make sure to consider this as the main
case and the main difference about different types of complete trees we could receive.
So from here, let's move on to actually verifying any constraints about the problem.
The question, again, is pretty straightforward, there's not that many constraints that we need.
We know that if we get a empty binary tree, we can just return zero since we're just counting nodes
here.
So let's actually write out some of our test cases.
To save us some time, I've imported in the three complete binary trees that we have just seen here,
when you come up with the actual test cases yourself, you want to think about the fact that it's a
complete treat.
This means that every level is completely full, except for the last level where if there are nodes,
they must be pushed as far left as possible right away to conditional cases should jump out at you.
The first one should be where the level is completely full.
The other is where the level only has one value.
The third case here can be any one in between where it's not completely full.
But it's also not just one value in this case.
This tree represents the case where it's any number of values filled as long as they're completely to
the left.
These three conditions may not necessarily contribute one hundred percent to all of the insights that
you'll need, but at the very least, it's a good place to start.
As far as what might jump out at you and what your intuition might tell you that you want to consider.
So at this point, you might also be thinking this solution seems a little bit way too obvious.
When we think about whether or not the traversal matters.
We know that we want to navigate through the tree to count the nodes, but we don't really care about
the values inside since we're just counting notes here.
We also know that our breadth of research and depth research traverses both take a time of of ln the
spaces also generally of NP.
And if that's the case, both before a search and deafer search work, because they each touch every
node a single time.
And what we're doing is essentially just accumulating the count for every node that gets touched.
So breadth of research or depth research are both valid and they seem like there's very minimal code
changes to implement in order to implement that solution here.
You want to voiced this concern to your interviewer.
You just want to say that it seems really obvious that I can leverage breadth of research or depth research
and just count the nodes along the way.
But there must be a more optimal solution.
And your interview will probably respond back.
Yes, you're correct.
There is a more optimal solution here and from here.
You want to say that?
Let me focus in on the fact that it is a complete binary tree because the complete binary tree is the
real trick to this question.
The fact that we received a complete binary tree and the fact that the question seems so obvious to
implement means that the complete binary tree itself is the challenge.
We need to figure out what kind of insights we can derive from a complete binary tree to bring the time
or the space down from zero of.
So when we think about that, we let those two things guide our thoughts.
What is lower than oh, then there's only of log ln and low of one.
If this is the case then that means that in order to solve for this problem, we want to achieve something
within this realm of Lagann or one.
So let's look at the structure and think back even before binary trees.
What are the things that we know that can achieve log n that are somewhat tangentially related to the
structure?
Well, this shape kind of looks like our divide and conquer pattern when we think back on Quicksort
of Mursau and the pattern that we had, we originated with the full array and we would divide it in
half and divide those in half and keep going until we had singular values which are easy to sort.
What we knew was that that shape looks pretty much like a complete binary tree that's also full.
So here, what are the insights we know about that?
Well, let's look at the height of the tree.
When we think about the height of a tree that is completely full, the number of nodes there are, we
can represent as an.
What we also know is that this is essentially a log base, two of N, which in our case here and being
15 yield's us three point nine something which is pretty much just for.
What we also notice is that four is the number of levels that exist in this tree.
So here there is some relation to log.
And what we also know is that the values inside of the very bottom of this tree are an over two.
I've taught you this before about complete trees.
When we analyzed looking at breath research and the size of our Q holding all the values in a full bottom
level of a complete tree here, this is an over two and maybe this is also significant in some way.
So I want you to think about all of these things and just try and figure out, at least with your intuition,
what kind of insights might be impactful regarding these complete trees.
In the next lesson, I'm going to show you how to actually solve this problem.
But I do want you to try and see if you can figure it out.
There are a lot of tricks here, but it mostly revolves around thinking about the shape here and thinking
about what different things we have that can achieve log of.
And it's not just the height of this tree that's log in.
There's also something else that we have leverage before.
And the last thing I'm going to give you about that is binary search.
Can we combine all of these concepts together in some way regarding these binary tree questions to come
up with an optimal solution?
I'm going to leave that to you to try and I'll show you how to do it in the next video.