5.4 Binary Tree Representation |Array representation of Binary Tree | Data Structure

so in this video I'm going to talk about a representation of a binary tree or you can say sequential representation of a binary right say they have discussed a bubble sort selection insertion quicksort and mergesort okay so the next topic was heap sort but before going to heap sort I think you should know some basic terminologies that would be used in heaps or one of that thing is array how the binary tree is represented using aring so first of all I am going to discuss with this thing and after that we are going we are going to switch to heap sort in next we do fine it is also known as sequential representation of a binary tree now I hope you everybody know what is a binary Alesi binary it means two so node can have at most two children either 0 1 or 2 children not 3 children at most 2 children fine now let us suppose this is a binary tree fine and how this now this in pictorial representation in this this is a pictorial representation of a tree fine you know on whiteboard I can draw this thing like this but while writing a program or in your PC you cannot draw this thing you have to represent it using some another data structure fine so two methods are there one is this tree can be represented using array that is sequential representation and second method is this tree can also be represented using linked linked lists fine that is known as dynamic node representation right now see in array also somewhere somewhere you find out that when you are representing this tree in our array this mind you to you know array then index would be studied from 0 and somewhere you find out that in array the index would be starting from 1 so I am going to discuss with you both the cases this is case 1 and this is case 2 fine now how in this array we can represent this tree see node of this tree is ABCD up to I fine simple simple thing is we are going to start from root and we are going to fill this array level by level and from left to right from this level zeroth level first of all this level then this level that this level and then this level how C I'm going to consider this case one I'm going to start the Sarah from 0th index fine so first of all I am going to start with a this level then this level and from left to right not from CB B and C so here B and C the next level from left to right d e f g the next level H and I this is how we are going to represent this now see we in this by looking at this way you can say that C is child of a or you can say a is parent of B and C but if this is an array and I am saying that you don't have this representation and you have this thing and I'm going to ask you which node is child of which one which node is parent of which one obviously by looking at this thing you cannot tell right so there should be some formula there should be some relation to know which note is parent of which one which node is child of which node so now what are these formulas okay I'm going to take suppose this is is index I is 1 here I is 2 here I is 3 like this okay and in this representation you can say that a is at index 0 it is at 1 it is a 2 3 4 5 6 7 & 8 like this fine so in this case how to find out that relation how to represent this parent-child relation so the formula is see if if a node is that I attend X fine I index means maybe at 0 1 2 3 and up to 8 any node you can say a of I the suppose any name is I'm not taking a I'm taking suppose M so M of I a node is at M of I location now it's left child would be at which location so for that thing left child would be at which location 2 into I plus 1 and right child would be and right child would be at 2 into I plus 2 and to find out parent if suppose an if' index and the you know I 8 is 6 I have G and I have to find out parent of this G using this formula you can find out left child and right child how to find out parent so parent would be parent would be at which location I am minus 1/2 and we are going to take Slovenia and if you are taking this case suppose we are going to start index from 1 I'm going to write ABC here B here here F G H I I for this case to represent the relation between parent and child which one is child of which one which one is parent of which node the formula would be so in case 2 in this case fine if node has at index I attend egg suppose in this Arian the name of array suppose n so node is at n of I location so left left child would be so left side of that node which is at I attend X in this case would be at which position at 2 into I and right child would be 2 into I plus 1 and same parent would be parent would be at I divide by 2 and floor value so in the both the cases these are the formulas to find out left child right child and parent when you are going to represent you have when you are not having this pictorial representation you are having this array representation now you can verify these formulas see let us take in this case case one this is case 1 we have I value as for fine and here we have e ok and you want to find out suppose parent of this e how to find out parent will be at I minus 1 divided by 2 4 minus 1 / - and floor value that is 3 by 2 3 by 2 floor value 3 by 2 means 1.5 and if you are taking floor value then it would be 1 now go to the index 1 here we have B so you can say B is parent of e here you can check B is parent of E now suppose say is don't is not having any left side no right child and if you were to find out the left hand right child now is for left style would be add 2 into 4 plus 1 that is 8 plus 1 that is 9 but we are not having any ninth index and right child would be 2 I plus 2 that is at n so no tenth index we have fine so you can say that E is not having any left childhood right cell you can easily check he is not having any left side lower right child in this case if I am saying in this case suppose I is this one B okay so I am taking I is equal to 4 and at 4th we have B now find out the left and right child of this D this would be 2 into I 2 into 4 that is 8 so 8 at 8 index we have h so left child of this B is H left child of this DS edge you can easily check from this tree fine what about right child 8 plus 1 that is at 9th at 9th we have I so here we have right she'll that is I so if you don't follow these formulas and and if you have a tree and if you fill that array starting from root level by level and from left to right like this ABC and like this I have filled here then automatically these formulas would be held no need to check for these formulas fine but if you have this array and you are supposed to find out the relation about what is parent who is parent to a child and like this then using that formulas you can find out so now let us take this example I have this tree I have just changed a little bit a previous one we have two child of B in this we have two child of this II so sometimes many students make a mistake that we are simply just write down from the root in level by level and from left to right d e f g and then h and i same representation but that is not correct representation fine the very important point the very important point in this case is the tree the the binary tree which is given you how to make that binary tree a complete binary tree that is very important fine now what is a complete binary tree C incomplete by literally all the levels all the levels all the levels of a tree are completely filled except except possibly the last level fine first condition is all the levels are completely filled except maybe the last level is not completely filled now if flat last level is not completely filled then here also one condition is there so and the last level all the nodes are you know as left as possible fine so this is not a complete binary tree all the levels are completely filled this is the last level all the levels above this level are completely filled fine every node is having two child so this is completely filling the one condition is true but at the last level see these B's child should be as left as possible left means from this side from this side I am we are going to fill we are going to write the child so to make it a complete binary tree we are going to insert empty node one is here and one is here fine and here h and i now this is a complete binary tree fine now how to represent this in array simply from root a a B c d e f g d e f g but here here we have two blank child so we cannot directly put H and I you have to you have to keep the space blank to space one for this and one for this now you can write down each end I hear you can write down each end I and this would be 9th and 10th same in this case we cannot write H and I at this place after G to child are blank so you should keep these two space after G one for this one for this one and after this you can write down each end I index would be at 10th and 11th if you represent this true like this then only these formulas would be would be held fine let us suppose you are not taking this space free and you have represented this H here and I here rather than here and here now find out for H which is the parent according to this representation now H is at index I is equal to 7 and we are going to start from 0 so I am going to consider going to consider this case parent node would be at I minus 1/2 7 minus 1/2 and floor value means 6 by 2 that is 3 so go to the third index here we have D now according to this representation the parent of H is B but here the parent of H is e naught D and this these formulas are not going to hold in this case why so because you are not keeping these two free space so if you write down if you write down H and I at this place then find out the parent of H now H is at index ninth now parent would be 9 minus 1 that is 8 divided by 2 that is 4th index now go to the 4th index here we have e here we have e now H is the parent of h is e that is right representation now let us take another example see now if you have this example is this a complete binary first of all check yes it is a complete binary why because although this is the last level but all the level except this last level is completely filled that condition is true and the nodes and all the keys in the last level is left as left as possible so we have only one key and which is a leftmost side to say simply representation would be after a b c e f g you can simply write down here h here you can simply write down what h no need to do this when the space and the array would be from 0 to 7 here also you can simply write down h the array would be from 1 to 8 now let us take this example I have only this binary a B and C now first step is how to make it complete binary you cannot simply write down a B and C find in array that would be wrong that in this that case this formulas will not be held fine now to complete it a binary ready complete binary tree here would be one blank child and at this level also we have this blank and this blank right because C this is the last level this is the last level so except last level this level should be completely filled so now this level is completely filled now second condition is at last level the the child would be the node would be as left as possible fine so C this one child is there at there as at the last node and this is at the rightmost position so obviously you have to fill all the left positions so here also we will insert a blank node so this is now a complete binary and how to represent this in an array I'm just going to take case one from 0th index 0 we are going to start from root a then next level from this left side this is blank fine next we have B next level have blank we have blank we have blank and last we have C 0 1 2 3 4 5 & 6 so the size of this error is 7 although only 3 nodes are there but the size would be 7 so wastage of space is there in this representation why and if you have one more child here like B now what you will do then you'll have to make it a complete binary tree like this only so you have to insert blank node blank blank here also blank here also blank here also blinker to the left also blank now it is complete binary tree now how to represent this one obviously we are going to start from here a then blank then B then blank blank blank then C and after C 1 2 3 4 5 6 7 7 blanks would be there ok 1 2 3 4 5 6 & 7 and after that you would insert D 6 7 8 9 10 11 12 13 and 14 so see how many wastage of space is there in a representation so here you can say if asked you'd left or right skewed binary tree is there then in a representation the wastage of space is there so this is how you can represent a binary tree using array fine in next video I am going to discuss with you make seed min-heap and after that we are going to discuss heaps hot so till then bye bye take care

Channel: Jenny's Lectures CS IT

Views: 300,589

Keywords: binary tree, binary tree representation, array representation of binary tree, jenny's lectures, jayanti khatri lamba, ugc net, gate, GATE computer science, computer science youtube, cse, it, IT youtube channels, quick sort, bubble sort, selection sort, merge sort, heap sort, data structure, study material, engineering, complete binary tree, types of tree, dijkstra algorithm, floyd warshall algorithm, avl tree, b tree, binary search tree, avl tree insertion

Id: zDlTxrEwxvg

Length: 17min 50sec (1070 seconds)

Published: Mon Jun 17 2019