BINARY TREE REPRESENTATION - DATA STRUCTURES

[Music] hello friends welcome back to our channel so in the previous session we have started the tree concept and in that we have seen the tree terminology and then we have seen the types of vibrate leaves so in today's session we'll go with the another concept that is called the tree representation so how to represent the binary tree by implementation right so before going to the implementation part let us recall the definition of a binary so binary tree means a tree which is having every node with a at most two children that means every node of a tree should contain at most two children's that we say that 0 1 or 2 that means a maximum of 2 children so if that constraint is satisfied that implies that tree is a binary tree now we'll go with the representation part so binary tree representation so we can represent this trip while implementation in two ways so one is using in the media using in linear or sequential mean second one using the list concept using a list concept this is by using any concept right so both are linear or a sequential way but first one is by using the Harris the second one by using the least right now we'll go one by one so first using eros so first using arrays how and tree can be represented using a single dimensional array so you know that so we have to follow the 3 steps so by representing any tree into the and so first one the first step consider the root node and index 0 consider the hope load is at index 0 that means in every one-dimensional array the first element that means a 0th index element will be the root element next next one sorry I have not changed the left chain the left chain is placed it to i plus 1 to i plus 1 where is position of paint hey is a position of parent so we know that a pre can consist of a parent and a parent it will be having children the left two chain then right check so the left child is placed at the two I plus 1 where is the position of a parent so if it is a loop roll if it is a root for the root 3rd position is 0 so the left the chain of the hoop will be 2 into 0 plus 1 that is 1 and I change C and the right chain is placed it to I plus 2 and also where I is position of a parent right so we need to follow these 3 rules while representing any binary tree in a single dimensional and so the root will be concerned as a 0 and then every you have to change every left child will place it to I plus 1 and every night chain this place at 2 I plus 2 when I will be the position of a pivot so automatically the graph to channel means this left side will be having a pin right chain means right chain is having a parent so based upon the position of the parent we have to calculate the position of a right ear and left chain so the position of the left side will be 2 I plus 1 position of the my chief will be in the toy plus 2 right see let us take a simple example a B and C so how this can be stored in a one dimensional array and one image see let me do these are what I mentioned Larry this is 8 X 0 1 2 3 4 & 5 right so yeah yeah he's a hoot consider the custom consider the index you so simply place this at 0th index so ya is placed at 0th index next every to this b b is not a root word so every term will be having only one loop code right so the starting node will be the rope through so this is not a good one so B is it left to change off yeah so it is a fair enough so what's the position of u 0 so position of a is 0 now we have to find the position of B based upon the position of fruit or its pain so position of P position of B will be 2 I plus 1 because it is a left chain so here is a position of a so 0 it means 1 so position of B is 1 so at that wind takes one place similarly position of C position of C will be 2 n plus 2 because it is a right chain because it's a a chain when y is a parent what's the parent position of C parent is yay so what is the position of parent 0 so 2 I plus 2 it will be 2 so second index the C will be player so in such a way we have to find the position of left change and the might change based upon its parent position so the first and the root node index will be starting with the 0 and from that we can calculate the positions where I can find the positions of the children right let us take an example we'll follow the same rules so let us take an example and we'll follow the symbols see let us consider here a b c d e ya g ok see ya ya me see these having butsudan DNA these having only one children that is a left chain he is also having only one channel that is left to left chain so let us represent this one let us represent this one meet a single dimension see that right down the next zero one two three four five six seven eight nine ten eleven twelve thirteen fourteen fifteen sixteen seventeen see so a simpler place the a and the index yeah so this is the position Z now B is the left the child of a so it will be 2 I plus 1 is equal to 1 the position of B is 1 these are my chain 2 I plus 2 is equal to C next Big D is and left the change of B what is the pre position 1 so here I applied to I plus 1 is equal to 2 plus 1 it's a three okay two I plus 1 here the position of B is 1 so 2 into 1 plus 1 so 3 so in the third position we can write D here 2 I plus 2 so is a 1 right so here I is equal to 1 here I is equal to 1 here I is equal to 0 here also is equal to 0 so and he's the position of a pain right so I is equal to 1 so 4 and the whole we can write in here again so I is equal to parent of VFD so I is equal to 3 right I is equal to 3 so 2 I plus 1 is equal to 2 3 so 6 and 7 the position of Y F is 7 so here it will be placed and j g is equal to 4 here so 2 i plus 1 is equal to because it is also a left to change so 2 4 8 9 so my position okay so this is the error representation of the given tree so hope you understood this one so these will be in in peace and D these are all will be the empty so both are having only the left chase so we have to apply the formula to a plus one if it is having the right change we have it up in the purple y plus two when I will be in a position of parent of Y that is D D position is three right so from the root node we have to calculate this and we have to fill the and so this is how we can represent and binary tree into this array representation so hope you understood this concept right so we have to follow the three roots root will be 0 root will be at the index 0 and the bike chain sorry left chain will be at 2 I plus 1 my chain will be with 'edit to a place so simply following those formula we have to represent the 3 in a department I will go in the second representation second type of representation so that is a list representation list so here we use double link released the double link released right for representing each representing each node right so double English means we know that it is having three fillies right three fields this is an over all this is we can say this is a data or information this is the address of previous here the address of next right so this is how we can represent a node using the double entry list so here we need to represent the binary tree if you want to represent this binary tree see we can consider a node with the three fields see with the three fields so this is a data and this holds this holds the address of left chain and this holds the address of my chain right so every node of 50 can be represented by using this one so and data it is a headdress of left chained address of a night chain so this is how we can represent ad right so let us take an example hope you understood this one so let us take an example so consider an example this one a see okay so this is a binary because everybody's having a post to children now representing using the east so consider the route and serve the route cake right so this holds the address of another chain okay so that is B and this whole set address of another chain that is C and this holds the address of our the chain B this holds the address of another chain and this holds the address off under check yes and this holds the address of hundred children right so this is how we can represent the tree so this is the address of B here address off see here address of B here and us off e here address up here here the address of G so a of B means and this off no okay it is off you would be is represented as a of B similarly F we see you have div F of G yes these are the labels observe Saudis any phone is a leaf node yes and geoglyphs moves so this will be placed with an Molly so there will be no address further address right so how all these happen mark so this represents okay so hope you understood so this is another way of representing a binary tree using list so one is using arrays other one is using lists in the address we have to use a formula to a plus 1 or 2 a plus 2 so here we can use a doubly linked list for representing each node of hitting of a binary right by integral because binary tree means even node will be having it post to children so one is the left scale other one is the right chain right so hope you understood this one let us stop here and if you are having any doubts regarding this representation concept feel free to post your thoughts in the comment section so that definitely I will try to clarify all your dose and if you understood my sessions like my sessions share my sessions with your friends and don't forget to subscribe to our channel thanks for watching thank you very much

Channel: Sundeep Saradhi Kanthety

Views: 40,324

Keywords: sundeep, saradhi, kanthety, data structures, arrays, lists, stacks, queues, trees, graphs, primitive, non primitive, linear, non linear, linked lists, ds fundamentals, ds basics, nodes, structures, interview, placements, cse, edge, connection, parent, child, leaf node, depth, level, sub tree, root node, tree terminology, TREES IN DATA STRUCTURES, strictly binary, complete binary, perfect binary, full binary, binary trees, TREE REPRESENTATION, ARRAY REPRESENTATION, LIST REPRESENTATION

Id: QqkHLE1V-XU

Length: 17min 12sec (1032 seconds)

Published: Sat Jul 13 2019