BINARY TREE CONSTRUCTION WITH INORDER AND POSTORDER TRAVERSALS - DATA STRUCTURES

[Music] hello friends welcome back to our channel so in the previous session we have seen the how to construct a tree with the help of inorder traversal and the pre-order traversal so in this session we'll go with the another concept that is how to construct a tree with the help of inorder traversal and the postorder traversal right so you know that in order means right here in order Thanks the first leftish I left Chang will be visited and then a whole child will be visited and then the right chain will be visited and coming to the post order post ordered first the left chain will be visited then right chain will be visited and at last the route chain will be visited the last one will be the route so here in the post and us from the post order we will find the root node and from the in order we will find the right hand left right chained and left chain the same thing we will follow so in the previous session we have seen if it is a pre-order from the pre-order we will get the root Road and from the in order we will get the right chain left change you know here also the same but he from the post order we will find the road so we know that in the post order the mastaba will be the route so if you know the route road then from the inorder we can know what is a left shade and what is the right shape let us take an example so in order post Chardon so this is another at a poster duck now we have to find the thing we have to construct with you so from the in order from the poster we have to find the room so here from the postorder see post arteries left right in through so last evening dissolute the last segment will be the room so here the last infant is yay so a will be the route here so after knowing the hood we have to find the light right and left shades so other we have we will go with them in order so here EA is ignored so easy because in enid on the Left route invite so all the left shapes will be visited then who taught them right chain so with the help of room node we know that what is I have to chain and what is the right shape so here we can observe yay this is a loop roll all the elements which are left are left sub-tree all the events which are on the right earth right simply yeah only two elements one element it needs that right so V is in left child see is it right chain right so hope you understood this one so this is a very simple so with the help of a in order at the post order we can construct entry so with the help of for post order we will find the root end with the help of in order we will find the left subtree and why exactly and we will repeat the same process right so we'll go with another example right so let us take this example so in order and the post order so here for a root first we have to go with the post order see in the poster developed right so last segment will be the root so 1 is a root here and now we are supposed to find the left chance and high chance of this root so that can be fine and that can be done with the help of in order see here one is here so what are the elements on the left hand side those are the left chains right hand side up my chips 637 so among this four to five again we have to find the hoop roll that can be done with their first order so four to five C so four to five so in that in that it is a post order autonomous left to right and rule so what is the last element to so here the two is a right ailment I mean root element right so coming to the 637 in the 637 what's the last element three because the last segment will be the root 3 so 3 is in a root under Mike's entry now again there are two elements 4 & 5 here 6 & 7 and we are supposed to find the root and then we left at left hand kids so here we have find that boon as a root now we have to find whether fall on file as I left chains on my chains so further we have to take with the help of in order so go with the in order to is a root note so 4 is on the left side 5 is on the right side so forward to the left chain I will be the right shade happen to the 637 so 3 is a root here so 6 is on the left side and 7 is on the right side right so hope you understood this one so with the help of the postorder we will get the root because hoot is the last element so here in the post order the last element is 1 so 1 will be the root Eggman so in the inorder left root right so coming through with the help of a root node now all the elements towards the left side to the root the left sub-tree might say to the root of the right subtree so four to five and six 37 again in the four to file and we have to find the root so with the help of a post order 5 4 - so last payment will be the root so 2 is a loop road similarly 3 is a road so coming to the in order to is a root node so 4 is the left two and five is a right to the two so left Chinese for right Jen is fine here please ignore sixes are left to the three and seven is a right to the three so six is the left child and salmon is a right child so hope you understood this is the simple reconstruction with the help of you know during the post order traversal right so let us take one more example and just wear them see let us take it will take this example so the more number of nodes and now we have to find the binary tree construct the binding so with the help of post order we have to find the root in the post artists what in the last statement yay so a is a root move now coming to the right it has changed birthday in order so yeh here so there are more number of elements or towards the left hand towards the right so just to divide it so what are the inverse here HD i.e five elements here FC j & g 4 rivers so among these five elements again we have to find the root with the help of from post problem so if not most honest e HD i.e B so here post order the last element will be the Lu so be easy and coming to this one yes j GC c is a root because he is a last element so in the in this a proposed sort of C is the last element so you see will be the root now next again based upon the root node we have to find that where left and right chains with the help of in order coming to this this one being here so three events on the left chain one half it is on the right chain so so what are the three elements hitch D + IE invertible experiment a vitamin e only what I read is there right coming to the FC GD sees a report so f jg sees the route Lord yeah fizzy left chain only one change and coming to this right again there are two children J and G and we are supposed to find which one is the left which one is a root here in the HDI again we have to find the root so in order to find the root go with the postorder so go to the postorder HD i hid so last time medicine so hid last DS okay so based upon the root zone we have to find the left and right chains it can be H and I so D here H is on the left side is on the right side so H I okay now J + g j + g so in fact we'll have to find the hoop phone so in order to find the root don't go with the post order so go to the post Ronald J and G so these two jng last happened due to the who proved last element will be the root so G 0 G 0 okay now we have to find the left child and right change so here what if one thing it can be enough left chain on my chain so that can be done with the help of in order so J and G so what is the root node here G so G 0 G 0 so J is to the left of G so that means J is say you have to change of G so hope you understood this one so this is how we can construct a tree with the help of in order and the post order traversal so in the post order traversal the last one will be the rule so we will get the root node and in order to find the left-hand route I mean left and right change we have to be they in order traversal with the help of the in order traversal we can find the elements of a left subtree and elements of the fight circuit and just will repeat the same process and we can construct the binary tree right so hope you understood this one so if you are having any downswing adding this construction of a tree with the help of in order at the post order traversal feel free to post your talks in the coming comment session so the so that I will definitely try to clarify all your don'ts and if you really understood my sessions like my sessions share my sessions and don't forget to subscribe to our channel so I will post the link of this in order and the post order preorder outsells link in the description section so that we go through that and then you can follow the session so thanks for watching thank you very much

Channel: Sundeep Saradhi Kanthety

Views: 13,234

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, connection, parent, child, leaf node, sub tree, root node, tree terminology, TREES IN DATA STRUCTURES, complete binary, full binary, binary trees, TREE REPRESENTATION, inorder, preorder, postorder, tree traversals, left child, right child, BINARY TREE CONSTRUCTION

Id: sEnDVwYI1w0

Length: 12min 20sec (740 seconds)

Published: Mon Jul 22 2019