5.9 Construct Binary Tree from Preorder and Postorder traversal | Data Structure Tutorials

So here the very important point is if only pre-order and post order is given then it is not possible to construct a unique binary tree. I'm saying unique binary tree point. Second point is if only pre-order and post order is given then it is possible to construct a unique full binary tree. Okay. See you cannot construct a unique binary tree. you can construct a unique full binary tree. I'll show you how I we will take both the examples full binary tree also and for a binary tree also and I'll I'll discuss with you the full method of constructing the binary tree from pre-order and post order plus I'm going to tell you the trick simple trick how to construct a binary tree from pre-order and post order fine so let us take this example we have pre-order and post order is given now you are supposed to construct a binary tree fine see according to the method I'm going to tell you first of See what is the pre-order here? We have root, left and right. Pre-order traversal and post order traversal is left, right and root. Fine. Now first step is you're supposed to find out the root. How to find out the root? First element in pre-order is root and last element is also root. So f and f. So you can say f is root of the tree. Now you can say here you can write f. So now f is the root. Now next step is you're supposed to find out the left sub tree and right sub tree of this f. Right? So the next step is check out the successor of this f. Next element in pre-order is successor of this root is b. Fine. Now find out where is b in this post order traversal. B is at this place. Right? Now all the elements from here from starting to B would be element of the left subree. Fine. So the element of left subree are A, C, E, D and B. These are element of left subree. and remaining element are from H I G F we have already taken as root element. These are element of right sub. Now problem has been divided into two parts. This is the post order. Now see this post order this post order has been divided into two parts. This one and this one. So fine. So two sub problems are there for this sub problem. The pre-order is the pre-order is C. F we have already taken from B to this E. So Y till E. How you come to know that the pre-order is from B to E. You can see the element also. Next step is you can find out the predecessor of this root element in post order. In post order predecessor predecessor is G. Now find out where is G in pre-order. So here we have G. So from B to E the previous element of G till that element from B to E those element would be the part of left sub tree and from this G to last H element would be the part of right subree now we have again I'm writing pre-order is B A D C and E and post order for this sub problem is A C E D and B. Now I'm going to construct the lift sub tree first. Now this is the pre-order. This is the post order. Now again recursively you have to apply the same step on this thing. Now see how to find out root first element. This is root and here we have last element. Both elements are same. So B is the root from these elements. B is the root for left sub tree. Right? B and B. Now next step was find out the successor of this B in pre-order. Successor of root in pre-order that is A. Find out where is A in post order. Right here we have A. So all the elements from the starting to this A would be the part of left subree. But here we have only one element A only we have only A. So this A would be the part of left subree. and the C E D C E D these are part of right sub tree fine so left is over now this again problem has been divided into sub problems now here here post order is only C E and D now for this post order pre-order would be pre-order would also divided into two parts but see this is the sub problem that is over now for C E and D see here we have post order is C, E and D. For this sub problem, pre-order is divide this pre-order into two parts. This see A we have already taken. Now apply the same rule. Find out the predecessor of this root element that is D. Find out where is D in pre-order. Here we have D. So we are not going to take D. The previous element is A. So for this sub problem the post order is A and always the pre-order is also A. For this side we have only one element. This pre-order for this C E D is what? D C C and E D C and E. Right? Now apply same step again. Root is D. Here we have root. So here out of these element D would be the root. Now D we have taken find out the successor successor of this D in pre-order that is C. Now find out where is C in post order. Here we have C. So all the elements from the starting to C would be the part of left subree. But we have only one element C. So C is part of left subree. Remaining remaining element is only E. So E is the part of right subree because D we have already taken. So this is over. Now, now let us consider this right side because we have only con we have constructed this left sub tree. Now what about this one? Now for this sub problem post order is H I and G and pre-order is pre-order is G I and H g I and H. Right? So now find out root. Root is first element in pre-order G or you can say last element in post order. So from these elements G would be the root. So we have taken G. Now next step is find out successor of this root element in pre-order. In pre-order that is I. And next step is locate where is I in this post order. Now here we have I right. So now from starting till I all the elements would be part of left sub tree. So left sub tree part is H and I. So here we have H and I right and there is no right element remaining because G we have already taken. So right sub tree would be null. Okay fine. Now again we have this post order problem has been divided into two parts. So now post order is H and I and for this this pre-order would be pre-order would be G we have already taken I and H right again apply same step root would be I right root is I from these element only H is remaining now find out next element is H or you can say successor of this root element in pre-order that H. Now find out where is H in post order. Here we have H. Now all the elements from starting to this this element to till H would be the part of left subree. But we have only one element H. So at H is left sub tree and no right element is there. So right element so so the right sub tree is null. So now this is our binary tree from this pre-order and post order. Right? Now I'm going to tell you the simple trick. Now the simple trick is how to construct from pre-order and post order. See root is always the first element in pre-order. Okay fine we have F is the root. Now find out next element in this pre-order that is B. Right? Now where is B in this post order? B is at this place. Now if this this next element this this B this next element of this root which is in pre-order if this next element in post order is to the left of root to the left of root then that element would be part of the root. Now root is F and B is obviously to the left of this root. So this B is part of F either the left child of F or the right child of F. Right? Now here we have no left child, no right child. So first of all you are going to fill left child right? So here we will write B. Fine. Find out next element. Next element is A. Now find out where is A in post order. A is at this place. So now here A is to the left of B. It is also the left of F. But we are going to take what? B. We are going we are working on this B now. Right? So to the left of B we have A. So A is part of B and B is not having any left and right child. So we are going to fill first of all left child. So here we will write A. Next element is D. Find out where is D. Here we have D. D is to the left of this B. Right? Obviously it is left of F. But we are going to take first of all B because it is immediate left of B. So it is part of B. Fine. But B has already left child. So the remaining place is only right child. So here we will write D. Next is C. Where is C? Here we have C. Now C is to the left of to the left of first first element first root is D. Although C is left of B also F also but when we are going to when we are going to traverse this from left to right then first you'll find what? D. So it is part of D. So we are going to write to the left of D that is C. Next is E. Where is E? Here we have E. Traverse from left to right. First we first element you find is D. So it is part of D only part of this root D. So we are going to write to the right of D because left is already filled. Here we are right E. Next is G. Find out where is G. Here we have G. G is to the left of F. Right? So it is part of F. Now left is over because it it has left child is already filled. So right is only remaining. So here we will write G. Next is I. Now find out where is I. Here we have I. I is to the left of see when we are going to traverse this left to right from I. So first element is G. So it is part of G. So we'll write I here only. Next is H. Where is H? traverse this first element is I. So it is part of I. So we are going to write is we are going to write here to the left of I. So this is our binary tree using that trick. So see you can see that this and this are same. But I I already told you we cannot uniquely construct a binary tree using pre and post order. Now look at this binary tree. If you find out pre-order and post order for this binary tree, then you can find out the same pre and post order. You can find out and you can tell me in the comment box whether you are finding the same binary, same pre-order and post order for this binary tree or not. But see this binary tree is different from the binary tree we have constructed using our methods. Right? That is why I'm saying that if pre and post order is given only pre and post order is given then you cannot construct a unique binary tree because here we are getting two binary tree for two binary tree we are having same pre and post order right. So now this is the proof. So now second point was you can construct a unique full binary tree from given pre and post order. Now let us check I'm going to update in this also. See if if I if I make this binary tree as full binary tree then what should be the changes? See full binary tree is what? Every node is having either zero or two children. That is the only condition for full binary tree. Every node is having either zero or two children. Right? It's not like that all the levels should be completely filled or except last level or something like this as we have discussed in complete bindary. No, the only condition is every node is having only zero or two ch two children. Now for making this a full binary tree this child this node is having only one child. So I'm going to put one more child that is I and J and this node is only having one child and K. So I guess this is now a full binary tree right? Same we are going to make this as a full binary tree and we are going to construct this. So for this full binary the pre-order and post order is this one. Now I'm going to rub this. See I'm not going to take this one. And now suppose we have only this pre-order and post order. Now we are supposed to construct a full b sorry you are supposed to construct a binary tree. Fine. I'm going to construct using the simple trick because I have already discussed the meth method. You can apply that method and you can find out the binary tree. You find out the same answer. So now for root pre-order we will check the pre-order. This one is f first element is root. So this is root. F is root right? Now find uh check out what is the next element to this root in pre-order only. That is B. Now find out where is B in post order. Here we have B right. And this B is to the left of root. Root is F and B is to the left of root. Right? So it means B is part of F and part of F means either left or right. But here we don't have any child. So first of all we are going to fill left child. So here we'll write B. Next is A. In post order here we have A. So traverse the post order from left to right. First element find as from F to B. The element which are in the tree. First element is B. So it is part of B. So we are going to write here left of B. A. Next element is D. Find out where is D in post order. Here we have D. So traverse this first element find is B. So it is part of B. Here we will write D to the right of B because left is already filled. C. Here we have C and when you are going to traverse then it is it is to the first element is D and so it is to the left of this D right. So it is part of D. So to the left of D we have C. Next is E. Here we have E in post order. It is to the left of D. So here we will write E. Next is G. Where is G? Here we have it is to the left of F. So left child is over. It is part of F. Left is filled. So the only place is right. Here we will write G. Next is I. Where it I is at this place. Now the first element when you're going to traverse this from left to right first element is G. Out of these elements which are the part of now tree G. So it is it means it is a part of G. We are going to fill the left child of G. Here we will write I. Next is H. Where you have H? Here we have H. Traverse this. First element is I. So it is part of I. So here we will write to the left of I we will write H. Next is K. Here we have K. It is left of I. So it is part of I. Only right child is remaining. So we'll write here what? K. Next is J. Here we have J. It is part of G. Right? So left is child is filled. So only right is remaining. Here we will write what? J. So this is the binary tree using this pre and post order. So this is I guess the same first of all this was the tree and we we we made it a full binary tree and by inserting J here and K here this is full binary tree that is why we are able to construct this uniquely so you have to take care of this thing you can only construct a unique full binary tree from given pre-order and post order you cannot construct a unique binary tree from given pre and post order right now I guess you can apply the method on this thing because we have already discussed how the method is to be applied. If I apply the method on this thing then the video would be very lengthy. So I left this thing to you. You have to construct uh full binary tree or you can say binary tree from this using that method full method and you are going to tell me in the comment that you are going you you are finding the same answer as we have found using the trick right and the third is see suppose if I I make this bindary as full bind. So full for full binary tree here we will here I will insert J and here I will insert K see now for this this full binary tree the pre and post order is this one now question for you is you don't have this binary tree you just look at pre and post order you are given this pre and post order and you are supposed to find out you are supposed to construct a binary tree so try to construct a binary tree using the trick also and plus the method also so that you get familiar with both the approaches fine and just tell me whether you are you are finding this the same uh binary tree from this pre and post order or not in the comment box right so I'll see you in the next video till then bye-bye take