BINARY TREE TRAVERSALS WITH EXAMPLE - DATA STRUCTURES

[Music] hello friends welcome back to our channel so in the previous session we have seen the binary tree and the different types of binary trees and also we have covered how to represent a binary tree now when the session will go with the tree traversals three terraces so we know that our tree will be having a different roads and how to traverse each node of Italy so this term cells is of three types so in three different ways we can traverse an oak Supra tree so first one is in order you know order traversal second one preorder traversal third one post order traversal right so these categories are differentiated with the help of a group move so based upon the root node we can know whether it is a you know the Traverse self pre-order traversal or the post order traversal so coming to this inorder traversal so first they will be left to child left child and then the root node and then the right chain left change then root node then a right shape so theme will be appeared for the sub tree nodes so we will go with an example later so first we have to traverse all the left chains and then the root node and then the right chain coming to this pre-order the name itself indicates pre-order that means first a roof load which will be traverse after that the left shade will be traversed after that the my chain will be terms having to the postorder post order means a roofer will be at the last so first left chain right chain and native right so this is how we can apply this Traverse else so that means traversing the nodes of a trick now let us take an example of three notes a d NS C let us take an example this is a penalty right because so all the roots are having at most two two children so not more than two children right so coming to this inorder traversal of this tree first I left to change what is it up check be here so B then root node yay and the right role C so this is the inorder traversal of given binary tree coming to this one pre-order with the same example pre-order fruit load yeah let's move be right change C so this is the pre-order traversal for this given route bro so we have to visit all the moves we have to visit all the money's coming to this post order first will have change be right change see route them yay so this is a post order traversal for the given binary tree so this is how we have to visit the moves so the order to visit all the roads so forth in the in order first without to visit all the left change then the roof of then the right chain in the pre order first we have then you left child and then Betty and in the post or the first left check my chain and now we will take an example and we can solve right so what what is the pre-order traversal what is the post order traversal and what is the inorder traversal right so we will go with an example I will give you the example hey see okay so this is a simple binary tree I'll go with another one right so it is having all the power left shape it is having two children yeah okay here for P it is having only one children okay then he is having only one children that is also right chain next so this is a binary tree because here also every node is having not more than two check two children okay so at most two children so here the node every node of a tree is having a post Poochyena now coming to this in order in order means left root right right so coming to the left so here a is a room troll this one is in left subtree and this one is that right something okay coming to the left subtree first we have to work with the left subtree so again B is a parent or a root for this subtree so it is having the left D so first we have to write the left so D and then root for be what salute me B what is the right right chain there is no right chain so this subtree has been traversing okay then the leftmost of a is completed now root what's out you know right so again right is having them against subtree right so C is root root for this subtree C is a hopeful for some disagree so here also we have to apply the left turn on train so root this is the right subtree again this is having the right subtree okay so this is having the sorry left subtree this is a very gently again it is having is having a root because he is a parent it is having again subtree so first we have to write the left of the e which is not there so root the things right G so this completed okay this is all the left the child of C so this is computed next a root means C okay see now coming to the right right is having against of 3f h IE f is a parent that means it is a fruit right discipline for this subtree F is Arun okay so we have to play the same thing left on right so H yeah and right so a B c d e f g h fi okay so this is how we have to traverse all the nodes of a tree in in order travel three order terms okay three order terms pre-order traversal means so pre-ordered three order things first we have to write the route left and then right see if you have the real the route is yay so first we have to write the a and yeah is having this again and left subtree so in the left subtree be be be a parent so bt is also again one more left subtree so write this here okay so this is one more subtly so in that first we have to travel the route what's the route for this subtree be so be easy then left what's the left d then right there is no right child for would be so leave it so more to the right I mean okay first a route left we have completed the left traversal now move on to the right traversal so right is having again subtree where C is the route prefer the subject again C is having two children vnf which are having in again the chapter so this is one subtree so this is again one subtree and this is again on the circle okay so for the first we have to apply the hoop so we just write the C because it is a hoop for this subtree go with the he is again having children so first we have to write the hoop so he will be written and then left he is not having any left chain so leaving then right children so G so on the left subtree of C has been tiresome now go to the right subtree so rent is having a subtree with ESG fnh a so f is a root of HLA so first we have to go with the root so that's why yeah then left chain h and the left/right shape and so abcdefg hitchhike so we have to ask all the notes of entry so this is how we have to calculate this I mean we have to find the preorder traversal come to the post order traversal post order traversal means the route will be visited last so first the left should be traverse it then right should be traversing then route should be traps so we have to apply the same thing for the subtree zones like so coming to this complete three yes the route okay what's the left chain so this is a left subtree left subtree so first we have to traverse the left so we have to consider this left subtree so you miss you have to subtree again there is an other subtree with B and D B is a root in this sub tree we will be the root so left first you have to change should be travel so we have to say this D then my change will be traversal what's the right chain so right change this there is a row right chafer nor B so leaving then good what's the root B okay this is a left tail of left subtree of a now we have to go with the right subtree of here because a is a root which should be travel should last so we have to call it the rightmost or something here we are having a subtree with the root C and again we are having two sub trees with a root E and food yeah so coming to the left so left is something of C that means this one so here again is a rule for this subtree first left there is a lowly left chain so leave it there right chain G okay there Yee this one country did know who either right arrange something off see from the right subtree of see there is a wonderful tree it's a root yes yes H I first left that means H right that means a root that means yes and finally this left separately has been a traversal soul root must build it up so root is si si and further with the see the complete subtree of a has been completed so finally the root should be visited so II see it b c d e f g h tonight so here also we have traverse it all the nodes so this is how we have to calculate the inorder preorder and postorder based upon the rule we have to divide the sub trees and for each is subply we have to apply the same formula so that means if it is an inorder left root right increase the pre-order roots left right and if it is a post order right left right and root right so hope you understood this one so let us take one more example so that if you are having any doubts so everything will be right so let us take an example e so let us take this subtree sorry this binary tree so this is if you observe this is a complete binary tree because all the levels are having a mean every node is having 2 power L nodes okay every level is having 2 power elmo's right so now we have to apply the pre-order in-order and post-order for this subtree so let us take in order so in order please left root right so let us take this one just root right first yeah is the root node so all these are the left subtree and all these are the right subtree so coming to the left subtree again this is also a t okay so these root root here so first we have to traverse this left subtree then we have to go with the right subtree so in the left subtree again B is a note this is the left subtree this is the right subtree okay so coming to this left subtree again we have to play the same thing for sorry okay so we have to apply the left root right for the left change of this subtree be so left that means this one so again this is having a subtree with a root of B so left the root right so H D I so we have completed the sub thing left subtree of B now root root means B now right subtree right subtree also we have to right left to right so j yi okay so all the left subtree has been traversal now boot yay now coming to this right subtree again we are having two subtrees and so for C so when it's yes another one is G coming to the same I play the same for season three so again left left over C means this one so yes is there room for again because this is a subtree so again that's true train for this one so left L root yeah right yeah again root room for this separated C so C again coming to the right so right subtree again follow the same thing left to right so n G so this is the inorder traversal of the given subtree I mean given T so we will go with the pre-order 300 place first we have to traverse the route then the left then the right so we have to apply the same thing from all the sub trees so first then estate the a yeah is a route so first year will be Travis now left left means this one again in the left there are one sub tree get the root node B so write down the be here again for B there are two chains two sub trees left subtree right subtree will have two sub tree the root is deep again right the D so again it is having a chain enough to change H right chain and dis completed now coming to this one here also root left i'm so ii j k complete e left subtree of EA has been traversal now coming to the right subtree of VA right subtree of EA c again see the loop road so we have to traverse it because it's a pre-order see how many left to chain against subtree for subtree have fizzled so if y l m coming to the right subtree G n right so this is the order for the pre-order the pre-order terms okay having to the post order so just we have to remember one thing there is we're not gonna play the same rule for all subjects so left to right and route for the pre or post order left right and rude so coming to the left subtree so B is having a lesson 3 B is having two subtrees one is a left subtree right subtree left subtree is d h and i in this D H I for the left shape H right chain I root D so left subtree committed now right so right subtree in the right subtree again we are having subcribete e j and k here we have to see the left right cool so J is a left node right Road okay root node 3 so we have completed right left 3 right 3 no root that means blue so we have completed the left tree of J now border rights my tray of a in the writing of a we are having another sub tree with the pull chains so left is obtained by exactly coming to the left f is a root so L is a left Muslim Jeff is a root so L am here so they are completed the left subtree go to the right subtree in the right subtree also we have applies the same thickness right so right subtree yen which is a left sub nor left nor right road route so we have completed this one so what is the route for these two sub trees see so much to see so here we have completed the right subtree of Lee so guys have finally a we can write J here so this is the post order transfer so for simple example for this so for this tree these are the inorder traversal pre-order traversal postal codes just we have to follow the rule left root right root left right left right through so all this should be followed for all the sub things right so this is a very simple concept of it tree and also very important concept of it team right so hope you understood this session so if you are having any doubts regarding these try ourselves so feel free to post your dogs in the comment section so that I will definitely try to clarify all your domes and if you really 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: 53,824

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, strictly binary, complete binary, perfect binary, full binary, binary trees, TREE REPRESENTATION, inorder, preorder, postorder, tree traversals, left child, right child

Id: NWjFOr184vg

Length: 22min 56sec (1376 seconds)

Published: Sat Jul 13 2019