Hi everyone.
If you have a balanced binary tree, the height of that tree can be obtained by doing the floor of log
n, where n is the number of nodes in the balanced binary tree.
Now let's discuss the proof for this.
Now this is going to be divided into two parts.
In the first part, we will prove that when you take log n plus one again n is the number of nodes that
would be less than or equal to the height plus one.
Now if this is true now because this over here is less than or equal to h plus one the ceiling, or
when we round this up, we can say that we will get this to be equal to h plus one.
And then when we take this one to the left hand side, this becomes that ceiling of log n plus one minus
one is equal to h.
Now this is going to be part one of the proof.
Again I'm just outlining the steps over here.
And then we will see this in detail.
Now in part two we will prove that this part over here that is ceiling of log n plus one is equal to
log of floor of log n plus one.
Now if this is true, if we prove this we will substitute this part over here over here in the equation.
Now that would give us floor log n plus one minus one is equal to h.
And this minus one and this plus one will cancel out and it will leave us with floor of log n is equal
to h.
And that is what we want to prove.
Right.
So that is what we have over here.
Again let me repeat the height of a binary tree.
A balanced binary tree can be obtained as floor of log n.
Now let's proceed.
First we are going to start with the first part over here which is log n plus one is less than or equal
to h plus one.
And then from this we will derive that ceiling of log n plus one minus one is equal to h.
Now over here we have a balanced binary tree.
Now let's take a look at the number of nodes.
Over here we can see that we have one node.
Now in this level we have two nodes.
Similarly over here we have four nodes.
And in this level over here we can have a maximum of eight nodes.
Right.
So even if each of these four nodes has two children that's eight nodes.
So this is the maximum.
Now if you take a look at this pattern over here it's one plus two plus four plus eight etc. up to two
to the power h where h is the height.
Right.
So if the tree had just one node then the height is equal to zero and two to the power zero is equal
to one.
But if the height of the tree is equal to one, right?
So that would be something looking like this.
Now in that case over here we have two to the power one nodes.
So that's why we can say that in the last level we will have two to the power h nodes.
All right.
Now when you take a look at this this is going to be just a geometric progression right where you are
always multiplying with two.
So one into two gives you two, two into two gives you four.
And it goes on in this manner.
Now for a geometric progression we know that sum up to n terms is equal to a into r to the power n minus
one by r minus one, where this is the geometric progression.
So the first term is a and then we're just keeping on multiplying with r to get the remaining terms.
Now let's make use of this formula over here.
Now we can see that the first term is one.
And the number with which you are multiplying is equal to two.
So we can see that this sum over here is equal to one into two to the power h plus one minus one by
two minus one.
Now r is equal to two.
That's why we have two minus one over here.
And then n is equal to h plus one.
Right.
So notice over here.
So whatever is over here is one greater than what we have over here.
So over here we have h.
Hence we have h plus one over here.
All right.
So this is simplifying to two to the power h plus one minus one because the denominator becomes just
one.
All right.
So let's make some space over here.
So far we have seen that one plus two plus four plus etc. up to two to the power H is equal to two to
the power h plus one minus one.
Now in the case of the balanced binary tree, this expression over here is the maximum number of nodes,
right?
So why is this the maximum number of nodes.
It's the maximum because it's not necessary that the last level is completely full right.
So that's why we are not sure that we'll have two to the power H nodes over here.
All right.
So if n is the number of nodes that we have, then we can say that the number of nodes is less than
or equal to this much.
And we have already proved that the left hand side over here can be written as two to the power h plus
one minus one.
Therefore, we can say that n less than or equal to two to the power h plus one minus one.
All right.
Where n is the number of nodes.
Again why is this less than or equal to.
It will be equal to when the tree is completely full.
But if the tree is something like this where you can see the last level is not full, then it would
be less than two to the power x plus one minus one.
All right, so let's proceed.
Now we have established that n less than or equal to two to the power h plus one minus one.
Now let's take this minus one to the left hand side and apply log on both sides.
Then we get log of n plus one less than or equal to h plus one.
Now again how do we go from here to here.
Log of two to the power x.
And the base over here is two itself.
That's equal to x itself.
All right.
So this is this is something that's true again why is that.
So remember log of eight is equal to three.
And this three over here.
If if instead of eight you write two to the power three.
So this would be log of two to the power three.
And you can see this is equal to three.
So that's why log of two to the power x is x itself.
And hence when we applied log on both sides on the right hand side we are getting the power which is
x plus one over here.
All right.
So let's proceed.
Let me make some space over here.
Now we have that log of n plus one less than or equal to x plus one.
Now let me take this one to the left hand side.
All right.
So when you do that you can see you get log of n plus one minus one.
All right.
So this one is what we took.
The left hand side minus one less than or equal to h.
Now the maximum value that this can take is equal to h.
Right.
So that's why we can say sealing or rounding up this value over here will give us h.
So ceiling of log of n plus one minus one is equal to h.
And hence we have proved the first part.
All right.
So we have got that ceiling of log n plus one minus one is equal to h.
Now let's proceed to the second part.
All right.
Which is what we have over here.
Now let's say m is equal to floor of log n.
If this is true, then m less than or equal to log n less than m plus one.
Now why is that so?
Because over here we are flooring it right.
So let's say n is equal to eight.
In that case log eight is equal to three.
So that's why m is equal to log n.
In this case again m is what we are getting by flooring it.
And if you floor three you will get again three.
So that's why you have the equal to over here.
But then if let's say n was nine, in this case we would get three point something.
And then you can see it's actually greater than three which is the value that we get when we floor this.
So that's why we have m less than or equal to log n.
And then this would be less than m plus one which in this case would be four.
Right.
So this value over here is a decimal between 3 and 4.
So we have m less than or equal to log n less than m plus one.
Now let me clear this up.
Now let's take two to the power these values.
All right.
So we're going to take two to the power M two to the power log N and two to the power M plus one.
And the same relation would be maintained.
So we have two to the power m less than or equal to n less than two to the power m plus one.
Again remember log n when you do two to the power log n that's equal to n itself.
All right.
So why is that.
So let's take an example two to the power log eight.
And we know log eight is equal to three.
So this over here is two to the power three which is eight itself.
So you can see you have eight over here and here.
So that's why two to the power log n is n itself.
Hence we have n over here.
Now let me clear this up.
So we've we've got that two to the power M less than or equal to n less than two to the power n plus
one.
Now if I increase the value of n by one, I can get two to the power m less than n plus one less than
or equal to two to the power n plus one.
So this less than or equal to is now less than because I increase the value over here.
And then over here, I have less than or equal to because I increase this value.
This was previously less than.
Now again let's take an example.
Let's say n was eight.
In that case, M is equal to three right and two to the power.
Three is eight itself.
Now if you increase this eight by one, this was over here less than or equal to right.
Now when you increase this by one you can see it's definitely greater than what we have over here.
So that's why we have less than over here.
You can also think of it in this manner.
In the best possible scenario n would have been equal to two to the power M right.
It's it's again two to the power M cannot be greater than n because over here it's less than because
of the way the sign points.
So even if two to the power m is equal to n in that case.
Also, if you increase n by one, it would be less than.
So that's why we have less than over here.
And then we are increasing the value of n to n plus one.
So over here it was less than.
And this becomes less than or equal to.
Now again let's apply log across these three.
All right.
So over here we will get m over here we will get log n plus one.
And over here we will get m plus one.
So m less than log N plus one less than or equal to m plus one.
And because of this relationship because the maximum value for log n plus one is m plus one, we can
say ceiling of log n plus one is equal to m plus one.
All right.
And that is what we have over here.
Right.
Again that's what we need to prove this now because we know this.
And we know M is equal to floor of log n.
Right.
So that's what m is equal to.
All right.
Therefore let me just substitute this over here I can say floor of log n plus one.
So that's what is this over here.
Right.
Again.
What is it that we're doing over here.
We are substituting this.
We are changing what we have over here.
Ceiling of log n plus one.
Now ceiling of log n plus one is M plus one which is floor of log n plus one.
So I can say floor of log n plus one minus one.
This minus one over here is what we have over here x is equal to h.
Now these two cancel out and we are left with h is equal to floor of log n.
So this is the proof.
This is why the height of a balanced binary tree is equal to the floor of log n, where n is the number
of nodes in the balanced binary tree.