Hello all and welcome back.
So in this video let us continue our discussion on binary trees.
And now let's see what are the different ways in which we can classify our binary tree.
So let's get started.
Now in the last few videos we have actually dived a lot deep into binary trees as well as generic trees.
These are majorly the trees which we have seen, which we have built in examples in quotients.
Also, I have talked about their complexities, just that they will now be divided on some characteristics
for which I have created beautiful notes which you can refer in future as well.
And on the basis of those characteristics, they actually have some use case going forward on which
few of them we will be discussing a lot in depth.
So let's see all the different different types in which our binary trees can be classified.
So the first is on the basis of number of children okay.
So we know that a binary tree can have a zero 1 or 2 children at most.
Now we can actually divide our binary tree on the basis of that understanding.
The very first one is the full binary tree.
So type of binary tree in which every parent or internal node.
Okay.
So we know that internal node are these nodes has either two children or no children.
Okay.
So we have the example right in right of us, which is if this is your binary tree, it is a full binary
tree.
Because in this each and every parent either has zero children or no children.
What specifically that means is that one child is not allowed.
Okay, so that is the major crux of a full binary tree.
So that always it will be full for a particular node, either no child is there or we have two child.
So that's the very first division.
Now let us move forward.
The second one is the degenerate binary tree okay.
A tree in which each internal node has just one child, either the left or the right.
Okay.
So what we have changed in this particular type of binary tree is that now just one child is allowed.
So you can either have the child on the left or on the right.
Okay.
And the example is basically in the bottom of the definition where each and every node is having just
one child.
Now one thing you all will remember from our discussion on finding the diameter, where I was telling
you how exactly we work on the complexity of trees, right?
So here the overall height of my tree will actually be a lot high, right?
It is not balanced in a way we want our trees to be.
And it is analogous to.
Linked list.
Right.
So it is analogous to linked list.
In terms of operations because each node is just having one more node.
Right.
So you cannot make it balanced or you cannot have nodes on the both side, which means that it is just
like a linked list, okay.
Which is just connected a nodes which are connected to each other.
Okay.
Now the subtype or you can say another type is skewed binary tree.
In skewed binary tree it's again a degenerate binary tree only.
But it is dominated either by the left node or the right node.
So we are having either a tree like this where all are left, all single nodes are on the left side,
or this one where all are on the right side.
Now, we already had a discussion that how these are not the desirable kind of trees.
If we are solving any problem or doing any operation because the height becomes equals to n, which
is the number of nodes, and thus it takes a lot of time, or the complexity overall becomes very high.
But these are some defined types where you can or where they might be used.
And all the operations in these kind of trees are actually analogous to how they will be in a linked
list.
Okay, so great everyone.
I hope it is clear on the basis of number of children.
So this was the kind on basis of number of children.
Okay.
So either here 0 or 2 were allowed.
Here only a single one was allowed.
And in this the skewed one we just had a single but at one side.
So let us now move forward.
The second is on the basis of completion of level okay.
So the very first one is CBT known as complete binary tree.
Now they are actually used a lot in many concepts.
So what happened in this is a binary tree in which all the levels are completely filled, except possibly
the last level.
And the last level has keys as to the left as possible.
So keys basically we mean nodes here.
So we can maybe make it nodes in our definition.
And the nodes are as to the left as possible.
So we have examples towards the right where this is a complete binary tree.
So the idea behind making the complete binary tree is that you make a node and then you start filling
from the left okay.
You always make sure that you are filling from the left and then continue.
So it will never the case.
It will never be the case.
For example, this is not the complete binary tree.
The reason is that the nodes are not left, okay?
They are not on the left side as they should be.
Let me just undo it.
Great.
So a binary tree, which is something like this, let's say where you have made this particular nodes
and now you are making this right one.
It is not complete binary tree.
We want that the nodes should be as to the left as possible.
So in this particular tree, in this particular binary tree if you are adding an extra node but that
is towards the left, that is what makes it complete, because we are following a structure which is
like this while filling in our nodes.
Okay, so I will just repeat the definition once again.
Tree in which all the levels are completely filled except possibly the last level.
Last level can also be perfectly filled.
That is not the problem.
And the left last level has the nodes as to the left as possible.
So always start from the left and keep on filling it and you will get a complete binary tree.
Okay, great.
So now let us move forward with the second type is the perfect binary tree.
Now perfect binary tree is actually a binary tree in which it should be completely filled to the level.
And the child nodes, all the leaf nodes, they should be at the same level.
So a binary tree in which all the internal node has two children and all leaf nodes are at the same
level, so it will be completely proper filled like this.
Internal nodes.
These one, they are having two children okay.
So they always have two children.
And it is not that you can extend it like this where let's say it is having two children.
No.
If you are making the leaf nodes, they should all be at the same level.
So if you add another level, you will have to make sure that you fill in that level completely.
So that is what a perfect binary tree is.
It is perfect.
Perfectly filled.
Okay, so let us see some properties in this as well.
Few properties are there.
Now we can say that number of leaf nodes.
Leaf nodes count is equals to in this one plus internal nodes.
Internal nodes.
That is some property which we can see as well in front of us.
For this particular example there are three internal nodes and four overall leaf nodes.
The reason is that each and every node it will have two children.
Right.
So if I now just move this forward, this particular count okay, will of course be one less than if
I fulfill the last level completely, something which we can see here.
So three internal nodes, but we have four overall leaf nodes.
Because if we add leaf nodes here it is filled to the last level completely.
So they will be having four nodes.
And these two will be created with a single node as well.
So that's why this property always holds where number of leaf node is equals to one plus internal nodes.
Number of internal nodes.
Okay, along with that there is one thing more which we can notice.
The number of overall nodes is something like this.
So it is two to the power zero two to the power one two to the power two.
Right.
So on that note I can actually get that.
How many number of nodes are there?
Because I am sure that this will be completely filled.
Okay.
So the nodes what I can say is two h plus one minus one.
So it is just a GP, right?
Geometric progression where the number of nodes at each level is getting multiplied by two.
If I will create the last level here, let's say this level, then we know it will have eight nodes,
right?
Two to the power four two sorry two to the power three.
So on.
That this is the formula through which we can get number of nodes.
I hope that is clear as well everyone that it has these many nodes.
So if we just fill in let's say that we have overall height as three here three here.
So sorry two here.
Height is two here.
So two plus one will be eight sorry two plus one will be three.
So this will come out to be two two plus one minus one which will be equal to eight minus one equal
seven.
Right.
And we can see that we have seven nodes in this particular structure.
So this is what your perfect binary tree is.
Let everyone so let us move forward.
The last one in this is balanced binary tree.
Now balanced binary tree is something which we have again discussed a lot in depth.
A binary tree in which at every node height of left and right subtree for each node is either 0 or 1.
So we have done this question a lot in depth, where at each node we were calculating its height.
Left height right height and if it is balanced or not.
Okay.
So in this particular example the left height is three right is two.
So this node is balanced.
But if we have to make sure that we check this for each and every node.
The second I add a node here let's say this particular node.
Then this particular tree as a whole will not be balanced.
And the reason for that is this is a height three and this is minus one.
So it is two okay.
So this I think we have discussed a lot and that is all the division, everyone which we have on the
basis of completion of level.
Because here everything we talked about in terms of level, a complete one, it can just have everything
towards the left in the last level.
Perfect.
Everything should be completed at each level.
It should have all the leaf nodes at each level.
And last but not the least balanced where the difference between levels at each node should not be greater
than one.
So that is the all division which we get on the completion of level.
Now along with that, there are some binary trees which are special kind of binary trees.
Okay.
Now in our discussion of binary tree, we noticed that it was not having any property, right.
We were just discussing that how a binary tree can have either zero, 1 or 2 child.
So what we do in those special kind of binary tree is that we try to add some property to our notes.
Okay.
One such very famous binary tree is the binary search tree.
Something which we are going to discuss a lot in depth in the next module.
But I can give you an idea here.
So a binary search tree is a special kind of a binary tree in which the tree follows this property.
Left subtree contains node whose value is less than root value.
For example, if root value is four in this full left subtree, you will not get a single value which
is greater than four.
That is what a binary search tree is.
Okay.
So we are going to discuss this a lot depth in the next module as well.
But let's have a basic idea clear here.
So constraints which we are adding are something like this I have the root on the left of the root.
Everything should be smaller on the right of the root.
Everything should be bigger.
So these are the two constraints we are adding.
And the third one is that very important.
Each and every of these trees should also follow the BST property, which is they should also have the
same property.
So it is not that if let's say it could have been 1.5 here.
Okay.
So for example, if I would have changed this to 1.5 now it is still less than four, it is still less
than four, but it is not greater than two because this node also has to follow this full property.
Okay everyone.
So I hope this is clear as well.
Let me just remove this 1.5.
So this is where we have now added some extra constraint into our binary tree.
Now why we do that?
All these things we will discuss in the next module.
But that is another way we can divide our binary trees by now adding more constraints.
Okay, so that is the basic division.
More than what is required now.
I have also created a Python file where we have these diagrams.
So full binary tree, perfect binary tree, a complete binary tree and then the balance and degenerate.
Okay.
So this degenerate one is the slightly skewed.
But I hope you get the idea that exactly what it is we have seen them here or there, but the overall
idea is that we should be now completely clear on what exactly these kinds are.
Because they are used, they can be used in questions as well.
Okay.
In an interview or let's say in any online assessment where Mcqs are asked.
So you should have this particular knowledge.
Also for the perfect binary tree, I gave you few overall formulas like the number of leaf node is one
plus internal nodes.
How many nodes are there?
So all these things should also be clear.
I don't think they should be required to be memorized if you understand it properly the way we have
discussed.
And that is something which I will prefer just understand the overall learning.
Just understand how they are divided and don't actually remember anything.
You can very quickly get the same and once you do lots of questions, you will be able to identify in
question as well that hey, this seems to be a perfect binary tree to me.
This seems to be a complete binary tree to me.
Okay, so that is a level of comfortability which we are going to aim moving forward.
Okay everyone.
So great.
I hope all these types are clear.
I would just suggest you to once write all these types and try to recall what are all the properties.
They will be more than enough if you do this exercise two times.
That should help you to always remember what are the different types in which our binary tree is divided.
Okay, so now let's meet.
In the next module you will have to do some problems, some awesome problems which are designed for
you as well as some assignments.
So please make sure that you attend them properly and we will now meet in the next module where we are
going to start with binary Search tree.
Okay, so cool everyone.
Thank you.