Please likeeee, shareeee and subscribeeeeeeee :) Also follow me at Insta: Striver_79
@amishasahu15862 жыл бұрын
Understood sir!!!
@piyushacharya7696 Жыл бұрын
// NOTE: Q. How does inorder+preorder/postorder construct unique binary tree? -> Imagine that you have the following pre-order traversal: a,b,c,d,e,f,g. What does that tell you? You know that a is the root of the tree, this follows from the definition of a pre-order traversal. So far, so good. You also know that the rest of your list is the traversal of the left subtree followed by the traversal of the right subtree. Unfortunately you don't know where the split is. It could be that all of them belong to the left tree, it could be that all of them belong to the right tree, or b,c go left and d,e,f,g go right and so on. How to resolve the ambiguity? Well, let's take a look at the in-order traversal, what is its defining property? Any elements in the left subtree of a will come before a in the in-order traversal and any elements in the right subtree will come after a. Again, this follows from the definition of in-order traversal. So what we need to do is take a look at the in-order traversal (let's say it's c,b,a,d,e,f,g). We can see that b and c come before a, therefore they're in the left subtree, while d,e,f and g are in the right subtree. In other words, as position in the in-order traversal uniquely determines which nodes will be in its left/right subtrees. And this is great because we can now go on and solve the two subtrees recursively: pre-order b,c/in-order c,b and pre-order d,e,f,g/in-order d,e,f,g. And you can continue this recursively until all subtrees only contain a single element, where the solution is trivially unique. And since at each step we could prove that there is only one valid way to continue, the result is that a given pair of in-order and pre-order traversals can only belong to a single tree. NOTE: found this on Quora. It might help.
@nagame8598 ай бұрын
thanks, sir.
@ritikshrivastava94428 ай бұрын
one more thing to note u can construct unique bt only when all the values in bt is unique
@rishabhgupta122223 күн бұрын
@@ritikshrivastava9442 nope it depends on node's address and not value
@stith_pragya8 ай бұрын
Thank You So Much for this wonderful video..................🙏🙏🙏
@aswinikumarsahoo6459 Жыл бұрын
Recalled @Jenny's lectures CS/IT NET&JRF suddenly after 2 years, seeing the concept.
@sanchitsanyam7359Ай бұрын
Really Bhaiya , your effort means allot to Student community, Your videos are awesome.
@anonymousvoid63562 жыл бұрын
This guy has the same enthusiasm in all videos!
@priyanshkumariitd4 ай бұрын
thanks for awesome explanation striver bhaiya :)
@shauryatomer1058Ай бұрын
thanks for the great content
@pratikmhatre48158 ай бұрын
Very helpful
@bisssss216 ай бұрын
the best teacher
@user-tk2vg5jt3l3 ай бұрын
Thank you Bhaiya
@cinime Жыл бұрын
Understood! Such an amazing explanation as always, thank you very much!!
@judgebot73539 ай бұрын
thanks
@sysfailureexe60385 күн бұрын
Thanks u
@KartikeyTTАй бұрын
tysm sir
@ANURAGSINGH-nl2ll8 ай бұрын
Understand
@vivekreddy8204 ай бұрын
understood sir
@avanishmaurya20345 ай бұрын
Nice
@atharvakulkarni20242 жыл бұрын
Excellent Explanation!!!
@SHASHANKRUSTAGII2 жыл бұрын
If you have a perfect binary tree, then given only the PREORDER and POSTORDER, you can construct your unique binary tree Source: NPTEL IIT DELHI, DR. Naveen Garg
@niranjansaha5135 Жыл бұрын
if it is a perfect binary tree, then with a single order traversal we can construct the tree. Am I saying anything wrong???
@parthsalat Жыл бұрын
By perfect, you mean a complete binary tree, right?
@parthsalat Жыл бұрын
@@niranjansaha5135 I guess, you are right
@SHASHANKRUSTAGII Жыл бұрын
@@parthsalat right
@rishabhgupta122223 күн бұрын
@@parthsalat no its wrong both are different
@anshulbhardwaj26662 жыл бұрын
i best understood the concept from your videos sir thank you
@abhinanda70492 ай бұрын
understood
@poojabennabhaktula48832 жыл бұрын
Kudos to your effort!
@UjjawalSaranАй бұрын
🔥
@Yash-uk8ib2 жыл бұрын
sir, what is the reason behind the fact that the inorder traversal along with any one of the remaining two traversals gives a unique binary tree and why not any other combination??
@sparshsharma60682 жыл бұрын
I think that, Since In inorder traversal, we can identify the left and right subtrees of a node but, the same won't be true in the case of the remaining traversals. Consider the following tree: 1 / \ 2 3 / \ / \ 4 5 6 7 / \ / 8 9 10 Inorder traversal of this tree will be: [8,4,9,2,10,5,1,6,3,7] (LNR) postorder traversal of this tree will be: [8,9,4,5,2,6,7,3,1] (LRN) preorder traversal of this tree will be: [1,2,4,8,9,5,10,3,6,7] (NLR) Now, from this traversal, we can easily see that all the nodes on the left side of node 2 in the inorder traversal will form the left subtree. So that's why inorder along with post/preorder must give unique BTree.
@Yash-uk8ib2 жыл бұрын
@@sparshsharma6068 i think u have got a point!! Agreed!! Thanks for ur kind reply.
@sparshsharma60682 жыл бұрын
@@Yash-uk8ib Happy to help😊
@vibhu6132 жыл бұрын
@@sparshsharma6068 great Explaination
@sparshsharma60682 жыл бұрын
@@vibhu613 Thanks😄
@animeshmaru162 жыл бұрын
One exception for this is.. If we have only one node in binary tree then we can construct unique binary tree from preorder and postorder traversal. Preorder: 1 Postorder: 1 Unique binary tree: 1 (Root node) Sounds like funny but we can explain this edge case in interview and can have more advantage 🙂
@ShivamJha00 Жыл бұрын
bruh
@tarun_sahnan Жыл бұрын
if you have only one node that only there is no need for 2 traversal only one traversal will give you the solution. Preorder -> 10 10 is the root node
@editorera2392 жыл бұрын
Thanks bro for prior explanation
@DilpreetSingh-cs7yz2 жыл бұрын
why the inorder traversal along with any one of the remaining two traversals gives a unique binary tree and why not any other combination??
@priyanshkumariitd4 ай бұрын
Because we need to know not only the root but the left subtree & right subtree as well. So, one of the traversal should be inorder to identify UNIQUE BT.
@nileshsinha78692 жыл бұрын
Gonna complete the series tonight
@sangdilbiswal3018 күн бұрын
Hell yeah
@nagavedareddy58912 жыл бұрын
Huge respect ❤👏
@momilijaz2712 жыл бұрын
great tip!
@srivatsa11932 жыл бұрын
this is awesome !
@lavanyaprakashjampana933 Жыл бұрын
we love your content and we love you.....🖤
@user-jg2me8ry7l Жыл бұрын
you are just amazing sir
@amitswami31392 жыл бұрын
Very Good content striver
@tanishsharma5440 Жыл бұрын
Excellent Bro, perfect
@Professor-du2pf5 ай бұрын
"US"
@tanyagupta42472 жыл бұрын
understood!
@SatyamEdits Жыл бұрын
Hi Tanya ...!! Nice to see you ...again...!!! if you remember.....😅
@alesblaze4745 Жыл бұрын
thanks mate!
@bhaveshkumar68422 жыл бұрын
Thank you bro!!
@shivangisrivastava11582 жыл бұрын
Amazing 👏👏
@UECAshutoshKumar11 ай бұрын
Thank you sir
@cricketjanoon Жыл бұрын
Undersstod! 👍
@naman_goyal2 жыл бұрын
Best content brother
@parthsalat Жыл бұрын
Understood kaka
@Ayush-lq3fz2 жыл бұрын
understood :)))
@pawankumarpandit1822 Жыл бұрын
thank you striver bhaiya
@jaiminsolanki54782 жыл бұрын
Understood!
@vagabondfoodie5788 Жыл бұрын
Done till now 🥺🥺🥺 thankyou striver ❣️❣️
@Anonymous-uj3jx2 жыл бұрын
Thanks :)
@BG-lj6fw Жыл бұрын
understood.
@utkarshsharma66502 жыл бұрын
understoooood
@Sumeet_100 Жыл бұрын
Keep making this videos bhaiya
@dreamyme543 Жыл бұрын
Understood:)
@mriduljain198111 ай бұрын
completed lecture 33 of free ka tree series.
@jayyy311 Жыл бұрын
💚
@sujan_kumar_mitra2 жыл бұрын
Understood
@user-up6sl2gq8p8 ай бұрын
................
@stevefox23182 жыл бұрын
Bawaal🔥💪
@shreyasvishwakarma89792 жыл бұрын
noice video
@harshit8525 Жыл бұрын
Striver Bhaiya zindabad!!!
@09_himanshusingh442 жыл бұрын
Wow waiting for this 👍
@peddikarthik7832 Жыл бұрын
what if all the nodes have same value then answer wont be unique