Hi everyone!
In this video let's learn more about Binary trees.
Now understanding these concepts will prepare us to solve a variety of questions.
So let's get started.
These are the six topics which we will explore.
First, we are going to learn what we mean with perfect binary trees.
Now a perfect binary tree is a tree which has all its levels completely filled.
Now let's take an example.
So over here we have a binary tree.
And you can see this is level zero.
And this is level one.
And it's completely filled.
All right.
Now if the next level is filled it would look like this.
So again this also is a perfect binary tree.
Now if I have one more node in the next level, then you can see that this level over here is not completely
filled.
And therefore this over here is not a perfect binary tree.
All right.
So if this node was not there then we can say this part is actually a perfect binary tree.
All right.
Now what else.
What else can we observe about a perfect binary tree.
You can see that the number of nodes in the last level, which is this level over here is equal to one
plus the nodes which are there in all previous levels.
For example, over here we have four.
And in previous levels you can see we have three right.
So this is three.
And in the last level we have four nodes.
And four is equal to three plus one.
Again if the next level was filled let's take a look at how that would look.
So let me just draw that over here.
So if we fill this up you can see that in this level we have eight nodes.
So this is eight right.
So eight.
And in all the previous nodes together we have four plus two plus one which is seven.
So you can see eight is equal to seven plus one.
So the number of nodes in the last level is equal to one plus all the previous nodes.
So this is also something interesting about a perfect binary tree.
And then you can see that the number of nodes in the last level is two times the number of nodes in
the previous level.
For example, over here let's take a look.
We have eight nodes over here.
And in the previous level we have four nodes.
And this eight over here is equal to four into two.
So that's what we have over here.
So these are some interesting observations about a perfect binary tree.
Let's now proceed to point number two which is an almost complete binary tree.
Now this is a tree which should not be a perfect binary tree.
And then it's just that we have to fill the nodes level by level to it from left to right.
Now let's take an example.
Let's say we have one node over here and one node over here.
This over here is an almost complete binary tree.
Now if we have one more node over here, you can see that this is actually a perfect binary tree.
So this is not an almost complete binary tree.
But then if you have one more node you can see, yes, this is an almost complete binary tree.
And then when we fill the next node, we just have to make sure that we fill from left to right.
So we cannot add it over here.
So if you do that over here then this is not an almost complete binary tree.
All right.
So instead of that we should add over here.
So this is still an almost complete binary tree.
And the next node should be added over here.
And if we add one more node it will become a perfect binary tree if it's added over here.
So this type of a tree is called an almost complete binary tree.
So we have seen what a perfect binary tree is and an almost complete binary tree.
Now these two together is what we call a complete binary tree.
All right.
Now what is that that we can conclude this is a tree which has all the nodes completely filled, all
the positions completely filled till the second last level.
And in the last level, the nodes are filled from left to right.
And also it can have all the levels completely filled because a perfect binary tree is also a complete
binary tree.
All right, so we have understood what a perfect binary tree is, what an almost complete binary tree
is, and what a complete binary tree is.
All right.
Now let's proceed.
Let's now take a look at the next point, which is a full tree.
Again, these are just important terminology.
Now a full tree is a tree for which each node has zero children or exactly two children.
Let's take a few examples.
Over here you can see that every node has 0 or 2 children, right?
This node has two children, this node has zero children and this node has zero children.
That's the same case over here.
This one has two children.
This has two children.
And these nodes have zero children.
So this also is a full tree.
And this also over here you have two children two children, zero children, zero children and zero
children.
So this tree over here is also a full tree.
But then if you have this tree you can see this node has one child, right?
Therefore, this tree is not a full tree.
All right.
Now let's go ahead and continue.
Let's take a complete binary tree which is zero indexed.
And using this tree, let's try to find the range of leaves and the range of internal nodes.
Now let's take two examples and let's just mark the indices over here we are taking that this tree is
zero index which means this is index zero.
This is one this is two etc..
All right.
So let's write the indices over here.
Now over here you can see there are seven nodes.
That's why the indices range from 0 to 6.
And what about this tree over here you can see there are five nodes.
And the indices range from 0 to 4.
All right.
Now if you want to know the range of leaves.
And again remember leaves are just nodes without children.
So you can see over here these are the leaves.
And in this case these two are leaves.
And this one over here is a leaf.
Now in a complete binary tree.
If you want to know the range of leaves then all you have to do is you have to take flow of n by two
and you have to find n minus one.
So these will be the extreme indices.
So let's try it out in these two cases.
And again why are we studying this later when we study a concept called heaps binary heaps.
Actually these are complete binary trees.
All right.
So we will see this later.
Again we will discuss this once more when we encounter this.
But let's just introduce the topic over here.
Now in a complete binary tree we have seen that the range of leaves or the indices of the leaves will
be from flow of n by two to n minus one.
And again, this is the case where the complete binary tree is zero indexed.
All right.
Now what will be flow of n by two seven by two gives us 3.5.
And when we flow it we get three.
All right.
And n minus one which is seven minus one is equal to six.
So you can see that the range of the leaves are from 3 to 6 which is correct.
Right.
We have three four, five and six.
So that's working.
Now what about this case.
Let n is equal to five.
So five by two is 2.5.
And when we flow it we get two.
And n minus one is five minus one which is four.
And the leaves over here are two three and four.
So you can see it's working right.
So 2 to 4 has two three and four and 3 to 6 has 345 and six.
Now the other nodes will be internal nodes right.
So all the nodes other than the leaf nodes are internal nodes.
So we have already covered these.
And again when there are n nodes and they are zero indexed, all the indices will be starting from zero
and it will go on till n minus one.
So we have covered these.
So the remaining will be internal nodes.
So that would be zero to flow of n by two minus one.
And that's working over here.
Right.
We have seen flow of seven by two is three.
So if we subtract one from it we will get two.
And you can see that zero one and two.
These are the internal nodes over here.
And similarly in this case you can see zero and one are the internal nodes.
Flow of five by two was two two minus one gives us one.
And that's what we have over here one.
So 0 to 1 so zero and one are the internal nodes.
All right.
So we have covered these topics.
We have seen what a perfect binary tree is.
What an almost complete binary tree is, what a complete binary tree is.
And we have also seen what a full tree is.
All right.
And we have discussed the range of leaves and range of internal nodes.
Now let's just introduce one more topic before we end this video, which is tree traversal.
Now what do we mean with traversing a tree?
Traversing a tree means just visiting every node one time.
All right.
So for example over here we have this tree.
Now if we want to visit every node.
So we want to go to 35746 11.
So we would want to do that for multiple reasons.
And again in algorithm questions also you may need to traverse the tree for different types of questions.
Now we can do that in different ways.
All right.
So we will see this in detail when we discuss questions where we will see how we can implement breadth
first and depth first traversal in binary trees.
So we will see that in a future video.
But over here we are just introducing the concept.
So traversing a tree means visiting every node one time.
We can do it in different ways.
Now over here as an introduction let's discuss.
What do we mean with breadth first traversal or breadth first search?
It's also called BFS or breadth first traversal.
Now in this case, if you traverse or visit the nodes in the tree in this manner, we would visit three,
then five and seven, and then four and four, six and 11.
So three, five, seven, four, six, 11.
So you can see that we are visiting level by level.
So we are visiting the node three, then five and seven which are in the same level, then four six
and level 11 which are in the same level.
So this is what we call breadth first traversal.
And then we have depth first traversal.
Now there are different ways of doing a depth first traversal.
So let's not discuss that over here.
We will have a future video for that.
But over here let's just develop the intuition.
So in the case of breadth first we have seen that we are going wide first.
Right.
So we are going in this direction.
Now in the case of depth first traversal we would be going deep first.
So that means for example we could go from here to here to here.
So we are going deep before we are going broad.
And after going to four probably we go to five.
Then we go to six.
Then we come to three.
Then we go to seven and then to 11.
So that's again one way of doing a DFS.
But it can be done in multiple ways.
But the intuition that we try to develop over here is that in the case of depth first traversal or DFS
depth first search, we are going deep first.
But in the case of breadth first traversal we are going broad first.
All right.
And again traversal means visiting every node of the tree one time.