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

But before going to heap sort, I think you should know some basic terminologies that would be used in heap sort. One of that thing is array. How the binary tree is represented using array. So first of all I'm going to discuss this thing and after that we are going we are going to switch to heap sort in next video. Fine. It is also known as sequential representation of a binary tree. Now I hope you everybody know what is a binary tree. See binary it means two. So node can have at most two children either zero, one or two children not three children at most two children. Fine. Now let us suppose this is a binary tree. Fine. And how this now this in pictorial representation it this this is a pictorial representation of a tree. Fine. 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 list. Fine. That is known as dynamic uh node representation. Fine. Now see in array also somewhere somewhere you find out that when you are representing this tree in a array this binary tree in an array then index would be started from zero and somewhere you find out that in array the index would be starting from one. So I'm going to discuss with you both the cases. This is case one and this is case two. Fine. Now how in this area we can represent this tree? See node of this tree is A B C D 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 zero level first of all this level then this level then this level and then this level how see I'm going to consider this case one I'm going to start this array from zero index fine so first of all I'm going to start with A this level then this level and from left to right not from C 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 tree you can say that C is child of A or you can say A is parent of B and C but if this is a array and I'm saying that you you don't have this representation and you have this thing and I'm going to uh 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 node 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 i if index i is one here i is two here I is three like this okay and in this representation you can say that a is at index zero it is at 1 it is at 2 3 4 5 6 7 and 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 at if index fine if index means maybe at 0 1 2 3 and up to 8. Any node you can say a of i. The suppose array 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 + 1. And right child would be and right child would be at 2 into I + 2. And to find out parent if suppose at I index at you know I if I is six 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 -1 / 2. And we are going to take floor value. And if you are taking this case suppose you are going to start index from one I'm going to write a b c here d here e here f g h and 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 two in this case. Fine. If node is at index if index suppose in this area and the name of array is suppose n. So node is at n of i location. So left left child would be so left child of that node which is at i if index in this case would be at which position? at 2 into I and right child would be 2 into I + 1 and same parent would be parent would be at IID 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 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 one we have I value is four fine and here we have E. Okay. And you want to find out suppose parent of this E how to find out parent would be at I -1 / 2 4 - 1 / 2 and floor value that is 3x2 3x2 floor value 3x2 means 1.5 and if you are taking floor value then it would be 1. Now go to the index one here we have B. So you can say B is parent of E. Here you can check B is parent of E. Now suppose see E is don't E is not having any left child or right child. And if you are to find out the left and right child now I is four left child would be at 2 into 4 + 1 that is 8 + 1 that is 9 but we are not having any 9th index and right child would be 2 I + 2 that is at 10th. So no 10th index we have fine. So you can say that E is not having any left child or right child. You can easily check E is not having any left child or right child. In this case if I'm saying in this case suppose I is uh this one D. Okay. So I'm taking I is equal to four and at fourth we have D. Now find out the left and right child of this D. This would be 2 into I 2 into 4 that is 8th. So 8th at eth index we have H. So left child of this D is H. Left child of this D is H. You can easily check from this tree. Fine. What about right child? 8 + 1 that is at ninth. At 9th we have I. So here we have write child that is I. So if you don't follow these formulas and and if you have a tree and if you fill the array starting from root level by level and from left to right like this a b c 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 area and you are supposed to find out the relation about what is parent, who is parent, who is child and like this then using that these formulas you can find out. So now let us take this example. I have this tree. I have just changed a little bit. In previous one we have two child of D. In this we have two child of this E. So sometimes many students make a mistake that yeah simply just write down from the root a 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 have to make that binary tree a complete binary tree that is very important fine now what is a complete complete binary tree. See in complete binary tree 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 last level is not completely filled then here also one condition is there. So at 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 filled. One condition is true. But at the last level see these these child should be as left as possible. Left means from this side from this side I'm 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 empity node. One is here and one is here. Fine. And here h and i. Now this is a complete bindary tree. Fine. Now how to represent this in array? Simply from root a b c d e f g d e f gg. 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. Two space. One for this and one for this. Now you can write down H and I. Here you can write down H and I and this would be 9inth and 10th. Same in this case we cannot write H and I at this place after G two uh uh child are blank. So you should keep these two space after G. One for this one, one for this one. And after this you can write down H end I index would be at 10th and 11th. If you represent this tree 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 zero. So I'm going to cons going to consider this case. Parent node would be at i - 1 / 2 7 - 1 / 2 and floor value means 6x2 that is three. So go to the third index here we have d. Now according to this representation the parent of h is d but here the parent of h is e not 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 9th. Now parent would be 9 - 1 that is 8 / by 2 that is fourth index. Now go to the fourth 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 tree. First of all check yes it is a complete binary tree. Why? Because all the this is the last level but all the level except this last level is completely filled. That condition is true. And the nodes and the all the keys in the last level is left as left as possible. So we have only one key and which is as 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 one 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 you have to make it complete binary. You cannot simply write down A, B and C. Fine in array that would be wrong that in this that case this formulas would not be held. Fine. Now to complete it a binary uh sorry complete binary tree. Here would be one blank child and at this level also we have this blank and this blank right because see 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 see this one child is there at the 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 tree. And how to represent this in an array? I'm just going to take case one from zero index zero. We are going to start from root a. Then next level from uh this left side this is blank. Fine. Next we have B. Next level we have blank. We have blank. We have blank. And last we have C. 0 1 2 3 4 5 and six. So the size of this array is seven. Although only three nodes are there but the size would be seven. So wastage of space is there in this representation. Fine. And if you have one more child here like D. Now what you will do? Then you'll have to make it a complete bindary like this only. So you have to insert blank node blank blank here also blank here also blank here also blank and to the left also blank. Now it is complete binary tree. Now how to represent this one? Obviously we're 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 blanks would be there. Okay 1 2 3 4 5 6 and 7. And after that you will insert D 6 7 8 9 10 11 12 13 and 14. So see how many wastage of space is there in array representation. So here you can say if a skewed left or right skewed binary tree is there then in array representation the wastage of space is there. So this is how you can represent a binary tree using array. Fine. In next video I'm going to discuss with you max heap, min heap and after that we are going to discuss heap sort.