5.12 Construct Binary Search Tree(BST) from Postorder Traversal | Data structures

Now what is this postal traversal? As you know left here right and root root is at the last position. So in the last video that we have discussed pre-order traversal was given. We have find we have found out the in order traversal and then using both pre-order and in in order we constructed a binary search tree. The same method we will follow. In this case also postorder traversal is given. Now you have to find out the inordered reversal. As you know the property of binary search tree tray is when you find out the inordered reversal of a binary search tree then that inordered reversal would always be in ascending order. Okay that is for sure. Now how to find out in order reversal? See post order traversal is given then obviously elements in the BST would be these. Fine. Now in order traversal is what? Arrange these elements in ascending order. That is in order traversal of binary search tree. That is the rule. Okay. So in order traversal is five. Here we have 16 17 18 19 20 60 70 and 85. And in order to reversal is what? How to write? left, root and right. Fine. And pre-order traversal was root, left and right. We have already discussed how to find out all the tree reversals. Now see it is not like that you have to find out in order. After that you can only construct a binary search tree. No need to find out this in order traversal. Just from this post order reversal you can construct a tree. But we have followed this approach in the previous video. That is why I'm following this approach only. Okay, because that is very easy to find out in order traversal. Just arrange all the elements in ascending order. Okay, now how to find how to construct binary search tree. See, first of all, we have to find out root. Okay, how to find out root? To find out root you have to check post order traversal. Okay, see from in order traversal root is something somewhere in between left and right. So we cannot say which one is the root. But in post order traversal see root is the rightmost part. So we traverse this post order traversal from right to left. In pre-order traversals we have traversed that from left to right. I'll provide you the link in the description box. You can check it out there. So the rightmost the rightmost element is what root. So here 20 20 is the rightmost element. So 20 would be the root of the tree. Now second second step is you have to find out the left sub tree and the right sub tree of this root. Now how to find out that thing? To find out the left sub tree and right sub tree you have to check in order traversal. See now root is 20. Now find out where is 20 in this in order traversal. In in order traversal here we got 20. Okay. And this is root. Now see this traversal left root and right. To the left of root all the elements are should be in the left sub tree. And to the right of the root all the elements should be in the right sub tree. Now see this is the root. So this is the root and this is what left and this is right. So all the elements to the left of this root are in the left sub tree. So here we will write 5 16 17 18 and 19. In the right we have 60 70 and 85. Now repeat the same first sec first step and second step in this also at this uh sub tree also and at right sub tree also. Okay. Now the sol the problem has been divided into two parts. One is this and one is this. Now out of these elements, now first of all you can construct either the left sub tree first or the right sub tree first. It's up to you. I'm going to construct the left sub tree first. Now out of these elements which should be the root you have. First of all we have to find out the root. Then we find out the left sub tree of that root and right sub tree of that root. And to find out the root we check what? Posttor traversal. Okay. Now see out of these elements to find out the root we traverse the post orderer from right to left and we check out of these elements which which element is to the rightmost part in the post order traversal because root is always to the rightmost part in the post order traversal. So traverse this from right to left here this this this and this see 16 out of these elements see I'm not taking these elements out of these five 16 17 18 and 19 which element is to the rightmost part when we traverse this from right to left we got what first of all 16 so 16 would be the root here so out of these elements 16 would be the root now you have to find out what is the left and right sub tree of the 16 to find out this one you have to check in order traversal. Okay. Now locate where is 16 in this in order traversal. Here we got what? 16. 16 is the root. So same to the left. Check out root is in between left and right. So check out 16. The to the left of 16 we have only five. So this five would be to the left of 16. to the right of 16 out of these elements see I'm not taking these elements out of these element to the right of 16 elements are only 17 18 and 19 so we write here 17 18 and 19 fine now this is one element so you have to now apply same rule on these elements now find out which should be the root out of these elements to find out the root we How to to check post order traversal? So now check out of these elements which should be the root traverse this from right to left 17 18 and 19 which element you got first 17 18 and 19. See 18 18 is to the rightmost part out of these elements see to the left here 19 here 17. So 18 would be the root. So here 18 would be the root. So out of 17 18 and 19 18 would be the root to the left of 18 to the right of 18. To find out this case you have to follow you have to check the inorder traversal. Now locate where is 18 in this in order traversal. Here we got 18. Find out out of these elements 17 18 and 19 root is 18. So find out which element is to the left of 18. To the left of 18 only 17. So we'll write 17 this side. And to the right of 18 we have only 19. So here we got 19. So this left subtra finished. Now check out for the right one. Which should be the root? Check out the postal traversal. Traverse from right to left. Out of these element which element is to the rightmost part. Traverse is from right to left. 60. Out of 60 70 and 85. 60 is rightmost part because to the left we have 85 then left we have 70 to out of 60 70 and 85 60 would be the root. Now find out what is to the left of 60 and what is to to the right of 60. For this case check out in order traversal. Locate where is the 60 in in order traversal. Here we got 60. Okay. Now root is in between left and right child or you can say left or right sub tree. Now out of these elements 60 is the root. Now out of these elements check out the in order to the left of 60 which element is there to the left of 60. Out of 60 70 and 85. 60 70 and 85. No. No element is to the left of 60. So to the left of 60 we'll write nothing. 70 and 85 both are to the right of 60. So both we will write to the right of 60. 70 and 70 and 85. Okay. Both are to the right of 60. So we'll write here. Now out of these two which is the root press this post order from right to left. We got first of all 85. Okay. So 85 would be the root out of 70 and 85. 85 is the root. Now find out 70 is to the left or right. Obviously this is BST. So without checking in order traversal you can say 70 is less than 80. So we will write 70 here only and write child is null or after checking from in order you can say locate where is 85. Here we got 85. To the right of 85 we have nothing. So this is null and 70 is to the left of 85. So this should be the to the left side. So this is the BST binary search tree from this given post order traversal. You can find out the post order traversal of this tree and you'll get the same result as uh it is given in the question only. Okay. without in order also you can find out you can construct the binary search tree just trace out this from right to left 20 is here to the right side 20 is here to 20 would be the root obviously it is a BST then you can say all the elements to the left of this 20 would be less than 20 and all the elements to the right of this root is greater than 20 okay now find out a position I or you can say index I trace out this from this side to to this side. See first if 60 is greater than 20. 85 is also greater than 20. 70 is greater than 20. Now 16 is less than 20. Now find out the very first element which is less than the root element. Okay. So all these all these element would be to the left of 20 and all these elements would be 70 85 and 60. this would be to the right of 20. Okay. And repeat the same step without uh considering this in order again and again and you'll construct you can construct a binary search tree. So this is how you can construct a BST either by uh finding the in order traversal both uh using both post order and in order traversal or simply considering only the post order traversal you can also construct a binary search tree. Okay. So I'll see you in the next video. Until then, bye-bye. Take care.