5.2 Binary Tree in Data Structure| Types of Binary Tree| Data Structures Tutorials

in this video we are going to talk about binary tree its properties and its types right in the previous video we have discussed what is a tree and you can see that introductory part of trees right some basic terminologies which are used in pre as well as how to uh represent a tree the logical representation of a tree right the basics we have discussed now we will discuss the binary tree see now first of all what is a binary tree see it is a tree in which each node can have maximum two children or you can say at most two children right each node see as the name suggests binary binary means what two i mean zero and one so you can say in which a tree in which each node can have at most two children at most two means each node can have either zero one or two children but cannot have more than two children right that is a binary tree now how to represent a binary tree see if i draw something like this is this a binary tree yes see these are nodes this thing we have discussed already now this is having this node is having two children fine and these are having zero child so that is also fine this is a binary tree now is this a binary tree yes this is also a binary tree this is having only one node that is root node having no children that is possible we can have zero child a node can have zero child right so this is also a binary tree now see what about this one is this a binary tree yes this is also a binary tree see here each node is having this node is having one child one child and one child this is having zero child that is also possible now see is this a binary tree this is not a binary tree because see here in this case this node is having three children that is not possible we can have at most two children so this is not a binary tree right all these are binded trees this is also a binary tree right now if i draw something like this this this this end this this is also a binary tree the only condition is what each node must have at most two children if this condition satisfies that that is a binary tree now how we are going to represent this binary tree in memory that thing we have already discussed in the previous video see here this is the node each node is having what information plus may or may contain links that is not compulsory that each node should contain link to another node maybe if node does not have any child then it will not contain any link right so how you are going to represent this binary tree see this is a node first node is something like this three parts would be there this is what left child this is what right child you can say so here we have the data part you can say here i am storing one this is what left this is what linked to the right child so here we have one node this node is suppose having data two now see this node is having only left child so this is having only this link this link is null right so now here this is also suppose containing three values 1 two and three here i have four five and six because these node are having some information stored there three is not having any child node so there is no this link and this link would be null this is how we are going to represent this one here in this side we have 4 4 is having both left and right child so this is left and this would be right right here we can have 5 and here we have 5 and 6 both 5 and 6 are having no children so the links would be null right this is how we are going to represent the tree actually this is just a logical representation of a tree how we are going to store the tree in memory we are going to dynamically create these nodes we are going to set these links that thing also we will discuss the implementation of binary tree right now next thing is see now some properties of binary tree see we have discussed what is our level in the previous video this is not this is what level zero this is what level one this is what level two now at any level see at suppose i am taking at level one how many maximum nodes can be possible see at level 1 only 2 nodes can be possible maximum nodes here we cannot have 3 nodes because at most 2 children can be there now at level 0 the maximum node possible is only 1 right at level two the maximum node possible are see the maximum node maximum node can be here i have two here also i have two and two children of this node so this is what level two at level two we can have four children maximum we cannot have five six or something like this right this thing i guess you are getting my point now suppose i am increasing one level at this level at third level the maximum number of children possible are maximum means each of this node is having maximum children and maximum children can be two only it means one two three four five six seven eight right so here eight can be possible here four maximum here two here we can have zero simply same if i increase one level more then here at this level how many maximum number of nodes are possible you can say each this this node at level three each node will have two children so here i have eight nodes so eight into two that is sixteen can be possible so at level four sixteen maximum node can be possible right now how you can write this thing can i write here 2 raised to the power 0 can i write 2 raised to the power 1 2 raise to power 2 2 raised to power 3 and 2 raised to power 4 so now what you can say here at each level i the maximum number of node possible in a binary tree is 2 raise to power i that is one property right the maximum number of nodes possible at any level i is 2 raise to power i right this thing i have already shown you now next point may be the maximum number of nodes possible at height h the maximum number of nodes of a binary tree right at height h see at this level suppose i have three levels only now height of this tree is what height of the root node is equal to height of the tree height of root node is what one two and three go to the longest path find out the longest path path from the root or you can say from that node to the leaf node so now here height is three only right now at height three maximum number of nodes possible are see how to calculate you are you are supposed to add all these nodes means you are supposed to add first of all 0 plus at this level i have 2 plus at this level i have 4 plus at this level i have 8 it means you can say 40 number of nodes right maximum number of nodes fine now if i say height is only 2 right height is 2 means i am removing this level means now height is 1 and 2 height of root is two so height of tree is also two now if height is two maximum number of nodes possible are one two three four five six seven so how to calculate maximum number of nodes if height is h simply you will add all the maximum number of nodes at each level so you can say 2 raised to power 0 at this level 2 raised to the power 1 plus 2 raised to the power 2 plus 2 raised to the power 3 added till 2 raised to power h now this is what simply a gp series and how to find out the sum you can easily google it out i am not going to tell you this thing so answer of this would be 2 raise to power h plus 1 minus 1 right so maximum number of nodes of height h i am talking about this binary tree right so maximum number of nodes can be h plus 1 minus 1 right and if i ask you the minimum number of nodes if height is h then see minimum number of nodes can be h plus 1 how if height is this one 0 it means height is 0 means we have only one node right we do not have this thing we have only one node it means height is 0 so the minimum number of node is 1 if height is 1 see this is height 0 this is a tree binary tree having height zero minimum number of node is one now if height is one i am going to increase the height now height is one height of this tree is what one minimum number of nodes are one and two only minimum number of nodes i am not adding this node second node right now if you increase the height one more suppose i am increasing height one more now height is one and two now height is two and minimum number of nodes are one two and three if you increase one more now height is one two and three height is three minimum number of node possible are one two three and four so you can say minimum number of node possible are h plus one h plus one h plus one three plus one is four if height is one means this one one height one two two num two nodes are possible means h plus one minimum number of nodes are possible right next thing is if suppose you are given maximum node minimum nodes and you are supposed to calculate the height you can see the maximum height of the tree possible and minimum height of the tree possible then how you will see how you will calculate this thing now suppose you are given there can be n maximum nodes in the binary tree now you have to find out the possible height so maximum number of nodes are and as from this case we can say the maximum number of nodes can be of height h can be 2 raised to power h plus 1 minus 1 here you are supposed to calculate h value means higher i am calculating height of the tree now how you will calculate n plus 1 is equal to 2 raised to power h plus 1 i guess you can easily solve this thing by taking log on both side log of n plus 1 and log of see base is 2 2 raised to power h plus 1 now this thing is what log 2 n plus 1 log 2 base 2 is this one and this one is also 2. so here simply we can write h plus 1 right now here height you are supposed to calculate height is equal to low 2 n plus 1 minus 1 and here we are taking the ceiling function so this can be the height right but this can be the minimum height if maximum nodes are given those nodes can find out using those nodes you can find out the minimum height if minimum number of nodes are given that will give you the maximum height right now suppose minimum number of nodes are given n right n now height is what now minimum number of nodes of height h we know h plus 1 can be there now simply calculate the height is equal to n minus 1 so this can be n minus 1 can be what maximum height n minus 1 and minimum height can be this one log to n plus 1 minus 1. now we will see types of binary tree so types are full binary tree this is also known as proper or strict binding tree complete binary tree perfect binary tree degenerate tree and balanced tree also but balanced tree we will discuss when we will discuss the avl trees right that is also that is basically known as balanced tree now what is full or strict or proper binding tree see the definition is what it is a binary tree where each node contains either zero or two children or in another term you can say it is a binary tree see of course obviously it is a binary tree plus one more condition is it is con each node is containing either zero or two children or you can say each node will contain exactly two children except leaf node right now see what is a full uh binary tree now if i draw something like this is it a full binary tree yes because it is a first of all a binary tree plus here each node is containing either 0 see this one is containing 0 0 and 0 means these are leaf node right or two children this is containing two children this is having two children so this is what a full binary tree now see this is what is this a full binary tree no this is not why so because this node is having only one child but that is not possible in full boundary now see this is what is this a full binary tree yes this is a full binary tree right now see is this a full binary tree yes it is a full binder tree is this a full binding tree no but is this a full binary tree yes each node is containing either zero or two children or all the nodes are containing each node will contain exactly two children except leaf nodes except leaf nodes right now same the property of this full binary tree is what here number of leaf node is equal to number of internal nodes plus one here you can see this is a full binary tree now here number of leaf node count one two three four five and six number of leaf node are six right it should be equal to number of internal node plus one means here number of internal nodes should be five one two three four and five i have discussed what is leaf node what is internal node in the previous video you can check out that video if you don't know now what about maximum node and minimum node in this tree see maximum node is same as binary tree right because here also at this level at this level at this level means at every level i there can be two raised to power i maximum nodes and if height is at h then you need to add all the maximum number of nodes at each level so this is 2 raised to power h plus 1 minus 1 this thing we have already discussed right now what about minimum nodes see the minimum number of nodes height is 1 so the height is 0 so minimum number of node can be 1. if i am increasing height 1 this is height 1 so minimum number of node can be see this is not a full binding tree we need a full binary tree so here you need one more node so 3 can be the minimum number of nodes now if you increase height one more time that is now height is one and two height of this tree is two but this is not a full binary tree you need to find out you need to satisfy that that condition also each node is having either zero or two children so this should contain two children this can have zero children because you are calculating minimum number of nodes so one two three four five five right if height is three i am increasing one more height one two and three here also you need two nodes so minimum number of nodes can be plus two that is five plus two is c so now how you can write down this thing c two raised to power h plus one minimum number of nodes now how to calculate minimum height and maximum height see the maximum nodes will give you minimum height this one minimum height so minimum height would be same as previous one as binary uh tree and plus one hair ceiling minus 1 right because maximum node are same but here the maximum height can be the minimum nodes are 2 raised to power 2 into h plus 1 so how to calculate if minimum number of nodes are given n how to calculate height 2h plus 1 h is equal to n minus 1 divided by 2 so here you will write n minus 1 divided by 2 now next is complete binary tree so now according to the definition of a complete binary tree see a binary tree is a complete binary tree if all the levels are completely filled all the levels are completely filled except possibly the last level fine plus at the last level we have one more condition see and the last level has the nodes as left as possible right we are going to fill the last level from left to right see now i am going to take one example see here this is the last level right and this is not completely filled because these these nodes are not having any child so that is fine in complete mind tree see we have told you i have told you except the possibly the last level all the levels are completely filled see now this level this level this level this is what completely filled right each node is having two child so one condition is true now second condition is complete binary is what in the last level the nodes should be as left as possible means we are going to fill the nodes in the last level from left to right you cannot leave these nodes free these spaces free and you cannot write here then child node right so you need to delete and if i shift here then this is what a complete binary tree now is this a complete binary tree no why so obvious see the from the the except the last level all the nodes are completely filled but second condition is what here the nodes should be as left as possible we have left this node blank and we have put children to this node that is not true in complete binary tree if this is also having two child then this is fine right now is this a complete binding tree yes because here the condition is not that each node is going to have exactly two children so at the last level you can have one child but that should be filled from left to right see here if you write this thing you cannot fill the right child first of all you will have to fill the left child right so now this is also a complete binding tree right and this is also a complete binary tree now see is this a complete binary tree no this is not because now this is the last level right so at the last level you can fill the node from left only so here you should feel the left child you cannot feel first of all the right child is this the complete binding tree yes this is a complete mandatory right somewhere it is also written as it is nearly complete binding tree fine now in this case also same what about maximum node and minimum nodes maximum node obviously this is a binary tree so maximum node are same that is 2 raised to power h plus 1 minus 1 maximum node in a complete binary of height h right now what about the minimum number of nodes here the minimum number of nodes are 2 raised to power h this thing you need to find out how the number of minimum number of nodes are 2 raised to power h i am not going to trace out this thing now minimum height and maximum height obviously minimum height would be same as the previous one because maximum nodes are same in all the three binary trees right now what is maximum height maximum height means minimum nodes will return you the maximum height so how you will calculate i am going to write down this thing you need to calculate this thing right so the minimum the sorry the maximum height in the complete minded tree is log n this thing you need to calculate how this is 2 raised to power h and how this is log n right so this is what a complete binary tree now perfect binary tree see a tree can be a perfect binary tree if all the internal nodes are having two children and all the levels sorry all the leaves all the leaf nodes are at same level right these two condition fine now see i am drawing one tree all the internal nodes should contain exactly two children so here these are leaf nodes but all the internal nodes are containing how many two children right but second condition is what all the leaf node all the leaves should be at same level but here see this is what level zero one two and this is what three so two leaf node are at level two two leaf node are at level three so this is not a perfect binder tree all the leaf nodes should be at level three so now how to do this thing [Music] now see these are leaf node and all the leaf node are at level three and all the internal nodes are having two children so this is now a perfect binary tree now see this is also a complete binder tree can we say it is a full binary tree yes it is also a full minded tree so every perfect binary tree can be complete binary tree and full binary tree but vice versa is not true see if a tree is complete by injury then it is not necessary that it is perfect binding tree if a tree is full binary tree then it is not necessary that it should be perfect binding tree right now see what is degenerate binary tree here in this case all the nodes all the internal nodes are having only one child that is known as degenerate tree so see this if you draw this thing here this is leaf node and one two three three are internal node and each internal node is having only one child so this is what a degenerate tree and you can say this is what a left skewed binary tree left skewed binary tree means if the nodes the internal node is containing only the left child then it is known as also known as left skewed binary tree see now this tree this is what this is also degenerate tree because each internal node is having only one child that is right child so it is also known as right skewed binary tree right now taking example of this is this a degenerate tree yes because see each internal node is having only one child this is having right child this is having left child right so this is also a degenerate tree we cannot say that it is a left or right skewed it is a mixture of both fine so i guess this is all about binary tree plus properties of binary tree we have discussed and types of binding tree right now in detail how to implement a binary tree that thing we are going to discuss in next video so i'll see you in the next video till then bye bye take care

Channel: Jenny's Lectures CS IT

Views: 677,510

Keywords: data structures tutorials, data structure and algorithms, what is binary tree in data structure, types of binary tree in data structure, binary tree and its properties, tree in data structure, jenny data structures, jenny's lecture, jennys lectures cs/it NET&JRF, what is binary search tree in data structure, binary tree in data structure, avl tree insertion and deletion, computer science youtube channels, cs it, what is tree in data structure, binary tree traversals

Id: vvey2QCs98o

Length: 24min 10sec (1450 seconds)

Published: Sat Oct 05 2019