So before starting the video, I would love to thank Releval for sponsoring this entire 3 series. So if you are tired of waiting for companies to respond to your applications through different job portals, the next few seconds are very very important for you. Because Releval by Anacademy is India's first hiring platform that can get you a job within a week itself, yes. All you have to do is to register for the Releval test and within a week your interview will be scheduled with India's top companies and the top budding unicorns.
So what are you waiting for? Make sure you check out the links in the description and apply for the relevant test because it is free Hey everyone, welcome to the first lecture of the free cut tree series. So today's lecture will be about introduction to binary trees What is binary tree? So as of now you would be knowing arrays, stacks, queues, link lists Those are linear data structure whenever I talk about trees They are hierarchical data structures. They follow in hierarchy.
Now what is in hierarchy? If you have seen in computers, you have folders, right? This is the initial folder that you have and inside that you have one more folder. Inside that you might have one more folder. Inside that you might have one more folder.
Inside that another folder. These kind of things can be represented using trees. Whenever I associate a term binary, that's basically 0 and 1. So a binary tree basically says Inside a guy, there can be at max two guys.
Okay, at max two guys. So, at max, like over here there are two guys, over here there is only one, over here there is one, over here there is one, over here there is no. So, whenever I say that in a hierarchical structure, I can have at max two guys, that is when I can call it as a binary trees. Okay, so that's the simple definition of a binary trees.
Now why is binary tree important because there are a lot of questions related to binary trees that are asked in Interviews, yes a lot of times you will find a question related to binary trees So that is why we will be having this entire series on binary trees. So before moving on Let's discuss about some terms Whichever is the head or starting whatever you can call it that that is known as the root of the tree root the starting point And if this is the node and it has couple of guys these guys are called the children Yes, these guys this is the children This is the children. Okay, for example, this guy is a children of this guy.
This guy is a children of this guy Okay, I hope you understood the children concept. If there is one guy beneath it, beneath it, whatever we have Those are children's. Cool?
Now there's one more concept leaf. This is known as the leaf node What's the leaf node? A node which does not have children's. Okay, that's known as the leaf nodes There's another concept as sub tree Now let's assume you're standing here okay and this entire portion okay this entire portion will be the subtree this portion will be the subtree for this node cool let's say you're standing here this entire portion will be the subtree let's say standing here this entire portion will be the subtree let's say standing here this entire portion will be the subtree okay the node and the beneath guys beneath guys are the sub-tree of an ode. Now there is one more concept which is known as ancestors.
What is ancestors? So if you stand over here, for this guy, this is the parent, this is the grandparent, this is the grand-grandparent, this is the grand-grand-grandparent. So basically all the grand-grand-grand-grand, whatever parents you have, these guys are called ancestors.
For this guy, this is an ancestor. This is an ancestor. This is an ancestor.
This is an ancestor. Okay. For this guy, only this guy is an ancestor.
For this guy, this and this is an ancestor. For this guy, this, this, this is an ancestor. So I hope you have understood the concept of ancestors, root, children, leaf node.
Now there is something, there are a couple of other terms but that are not important. You will, you're just requiring these terms in order to understand the tree series. So now let's talk about the types of binary trees. So 1,2,3,4,5 there are 5 types of binary trees.
The first one is full binary tree. What is a full binary tree? Every node will either have 0 or 2 children. Now for an example, I can say this is a full binary tree because this node has 2 children this node has 0 children, this node has 2 children this node has 0 children, this node has zero children. I can say this Also has a full binary tree because this node has two children This node has two children this node has two children this node has zero this node has zero this node has zero this node has zero So this can also be called as a full binary trees whereas you cannot call Something like this as a full binary tree why because this guy has two children But this guy only has a single children, so it either can have zero or eight either can have couple of children's okay I hope you have understood full binary tree now let's talk about complete binary trees now the next type is complete binary trees it states all levels are completely filled all levels should be completely filled except the last level okay and the last level has all the nodes as left as possible so if I draw one of the binary trees I can say that This is a complete binary trees because if you check the levels, this is what you call levels.
Level 0 or 1, level 1 or 2 level, like 1, 2, 3 you can call it if you refer it as one based indexing. This level has all the nodes, this level has all the nodes, this level has all the nodes. So all levels are completely filled.
Again I can call this as I can call this as a complete binary. This level is filled. This level is filled. This level has this guys missing. This level has these guys missing.
But again that's allowed. If you carefully read it, it says except the last level. The last level cannot have everything filled. Now can you have something like this? No.
Because it clearly states the last level has all nodes in left. This is on right. So this is not possible.
Whereas this is possible. The last level is not completely filled but the guy is as left as possible. Okay so this is again a complete binary tree.
So just need to make sure all the levels are filled and the last level if not completely filled everything should be on the left. Have you understood complete binary tree? The next type of binary tree is a perfect binary tree.
Basically states all leaf nodes are at the same level. So this is a perfect binary tree because you can see these are the leaf nodes and all of them are at the same level. Again, this is not a perfect binary tree because this is a leaf node, this is a leaf node and this is a leaf node.
So, they're not at the same level. It has to be on the same level like this is a binary tree because they are at the same level. So, that's the definition of perfect binary tree. Now, the next one is a balanced binary tree.
It states height can be at a maximum of log n. Well log n, n is number of nodes. For an example, if I give you n equal to let's say 8. Okay, so log base to n is around 3. So you cannot have a greater height than 3. That means you cannot have a tree like this. At maximum the height of the tree should be 3, like the height. and this is generally done to efficiently search or improve the time complexity we will be doing the other variant of binary trees that is binary search trees where we will be understanding this that's why I'm not going deep into balanced binary trees as of now what is the next one degenerate trees what is a degenerate tree whenever it's a skew tree for example if n is 4 this is something like this degenerate skew trees If it is going like this, it's essentially a linked list only, right?
A straight line. So that's the definition of linked list. Whenever every node, every node has a single children.
That's the definition of degenerate trees. So I hope you've understood the terms related to binary trees and the types of binary trees in this video. So I hope you've understood the entire explanation as well as the code.
Just in case you did. Please, please, please make sure you like this video because it took a lot of efforts to make this entire tree series. Also, if you wish, you can definitely drop in a comment that will keep motivating me to make such further series. Also, if you're new to this channel, please do consider subscribing because I'm going to bring in such more series in the upcoming future as well. With this, let's wrap up this video.
Let's meet in the next lecture. Bye-bye. Take care.