5.8 Construct Binary Tree from Postorder and Inorder with example | Data structures

so the next question is construct a binary tree from the even post order and in order traversal fine okay post order traversal is what left right and then root and in all it is left root end right now first at first step is to find out the root of our binary tree how to find out the root fine from in order traversal you can't find out route because root is in between left on left alright we can't say what is the root in this inorder traversal fine but from post order we can say which one is route how because root root is always in the last position so pre-order may have nakata we have scanned the preorder traversal from left to right but in post order traversal you will scan this traversal from right to left starting element is 8 now 8 would be root over binary tree now find out they living to the left of this 8 and the element which are to the right of this 8 left subtree element of left subtree and element of right subtree fine how to find out this left and right subtree will go to the inorder traversal now locate this 8 here we have this 8 this one is our root root root key left and we have left left and root K like me right make your gob na right element so you can say the right path fine so all the elements to the left of this root these are the elements of left subtree and these are elements of right subtree fine element of left subtree are nine five one seven two and twelve right and the element of right subtree are four three and eleven okay now construct this left subtree now see out of these elements which would be the root have to find out and we can find out the root element from postorder only right and second condition is you are supposed to scan this post order from right to left now the condition to find out this root is out of these elements see out of these elements the elements which is coming first when you scan this traversal from right to left that would be the first element would be the root out of nine five one seven two and twelve which element is coming first when you scan this find out for no.4 is that right part 11 is also right part three is also in the right part five when you scan from right to left the first element found is five out of these elements we are not considering these elements fine five could be the first then five would be root of this left subtree now find out left and right part of this five how to find out your go-to you know locate this five in this in order here we have fine now out of these element nine is to the left of five the right this 9 to the left of five and one seven two and twelve 1 7 2 n 2 well would form the right subtree of this fine fine now find out out of these element which would be the root the same step we would go to the post order scan this post order from right to left which is element is coming first we have 7 out of these elements fine 7 is coming first when you scan this from right to left now 7 would be the root of this right subtree of this 5 now find out the left element of the 7 and what does the right soil or you can say the right subtree of this same locate the 7 into this in order here we have 7 and out of these elements find out one is to the left of 7 so you will write 1 here fine and two and twelve are to the right of the seven fine so you'll write two and 2n here now we have two elements again find out the root out of this two and twelve find out the root again scan this post order traversal from right to left and out of this to n2l which one is coming first this 2l is coming first two is after two when you will go from right to left well is coming first so 12 would be the root now find out left or right left or right tonight here to help me pass away only one element so either it would be the left part either or to the right part fine so to find out this we have to locate this 2l in this in order to ever sell now find out two is to the left of this 12 fine to the left of root part so two would be to the left of this now we are done with the left subtree now go to this right subtree now out of these element which would be the root out of four three and eleven would find out clinically the same step we would go to the post order traversal we will scan this from right to left and find out which element is coming first out of four three and eleven four is coming first fine then four would be the root now find out the left hand right part of this for to find out left and right we would go to the inorder traversal locate this 4 in inorder traversal here we have this four fine and out of this element a remaining element 3 and 11 both 3 and 11 are right of this root C root K can write me the left may appear root K there would be nothing and 4 and 13 both are to the right of this for now here we have sorry 3 and 11 Hill 311 would be to the right of this for now top 3 and 11 find out which would be the root again scan this post order traversal and 11 is coming first so 11 would be the route now see what we left or right how to find out go to this in order traversal locate this 11 here we have this 11 and 3 is 11 is a route fine and 3 is to the left of this 11 fine so 3 would be to the left of this 11 right so now we are done with our binary tree fine this is a row by negative from this post or an inorder traversal if you want to verify it then you can find out post order and inorder traversal of this tree without you know checking without checking these 1 and if the post order and inorder traversal of this tree is same as given in this question then you can say it's all right binary tree ok so I'll see you in the next video till then bye-bye take

Channel: Jenny's lectures CS/IT NET&JRF

Views: 338,491

Keywords: inorder preorder postorder traversal, binary tree implementation, tree traversal, inorder, postorder, bst traversal, binary search tree program, binary tree and binary search tree, tree traversal questions, BST Insertion, types of binary tree, traversal, inorder tree traversal, jayanti khatri lamba, jennys lectures, construct binary tree from postorder and inorder, ugc net computer science study material, gate computer science, technical, technology, cse, it, cs/it, engineering colleges

Id: s5XRtcud35E

Length: 7min 34sec (454 seconds)

Published: Thu Jan 31 2019