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

so the next question is construct a binary tree from the given post order and in order traversal fine okay post rival is what left right and then root and in order is left root and right the first our first step is to find out the root of our binary tree how to find out the root fine from inorder traversal you can't find out root because root is in between left or left or right we can't say what is the uh root in this in order revers fine but from post order we can say which one is root how because root root is always in the last position so preorder we have scanned the pre-order traversal from left to right but in postorder traversal we will scan this traversal from right to left starting element is a now8 would be root of our binary tree Now find out the element to the left of this eight and the element which are to the right of this eight left sub tree element of left sub tree and element of right sub Tree Fine how to find out this left and right sub tree we'll go to the in ordered traval now locate this eight here we have this eight this one is our Root Root Root left we have left left and root right right element so you can say the right part fine all the elements to the left of this root these are the elements of left sep Tre and these are elements of right sub Tree Fine the element of left sub tree are 9 5 1 7 2 and 12 F and the element of right sub are 4 3 and 11 okay now construct this left sub tree now see out of these elements which would be the root have to find out and we can find out the root element from post order only fine and second condition is you're 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 first element would be the root out of 9 5 1 7 2 and 12 which element is coming first when you scan this find out for no four 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 only we are not considering these element elements fine five would be the first then five would be root of this left sub tree Now find out left and right part of this five how to find out we would go to in order locate this five in this in order here we have five now out of these element 9 is to the left of five so we will write this N9 to the left of five and 1 7 2 and 12 1 7 2 and 12 would form the right sub Tre of this five 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 seven out of these elements fine seven is coming first when you scan this from right to left now 7 would be the root of this right sub tree of this five now find out the left element of this seven and what is the right child or you can say the right sub tree of this seven locate this seven into this in order here we have seven and out of these elements find out 1 is to the left of seven so you will write one here fine and 2 and 12 are to the right of the seven fine so you'll write 2 and 12 here now we have two elements again find out the root out of this 2 and 12 find out the root again scan this postor reversal from right to left and out of this 2 and 12 which one is coming first this 12 is coming first two is after 12 when you'll go from right to left 12 is coming first so 12 would be the root Now find out left or right left or right only one element so either it would be to left part either or to the right part fine so to find out this we have to locate this 2 in this inorder traversal Now find out 2 is to the left of this 12 fine to the left of root part so two would be to the left of this 12 now we are done with the left sub tree now go to this right sub tree now out of these element which would be the root out of 4 3 and 11 Root find out the same step we would go to the Post traversal we will scan this from right to left and find out which element is coming first out of 4 3 and 11 four is coming first fine then four would be the root Now find out the left and right part of this four to find out left and right we would go to the in order traversal locate this four in in order traversal here we have this four fine and out of these element remaining element three and 11 both three and 11 are right of this root see root right left root K there would be nothing and four and 13 both are to the right of this four now here we have uh sorry 3 and 11 3 and 11 would be to the right of the is four now out of three and 11 find out which would be the root again scan this post traversal and 11 is coming first so 11 would be the root now three would be left or right how to find out go to this inord raval locate this 11 here we have this 11 and three is 11 is a root fine and three is to the left of this 11 fine so three would be to the left of this 11 fine so now we are done with our binary tree fine this is our binary tree from this postorder and in order traversal if you want to verify it then you can find out postorder and in order traversal of this tree without you know uh checking without um checking these one and if the postorder and in order traversal of the tree is same as given in this question then you can say it's our right binary trick okay so I'll see you in the next video till then bye-bye take care