L33. Requirements needed to construct a Unique Binary Tree | Theory

[@takeUforward]

Please likeeee, shareeee and subscribeeeeeeee :) Also follow me at Insta: Striver_79

[@amishasahu1586]

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.

[@nagame859]

thanks, sir.

[@ritikshrivastava9442]

one more thing to note u can construct unique bt only when all the values in bt is unique

[@rishabhgupta1222]

@@ritikshrivastava9442 nope it depends on node's address and not value

[@SibiRanganathL]

Dude loved the comment

[@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.

[@SHASHANKRUSTAGII]

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

[@rishabhgupta1222]

@@parthsalat no its wrong both are different

[@anonymousvoid6356]

This guy has the same enthusiasm in all videos!

[@stith_pragya]

Thank You So Much for this wonderful video..................🙏🙏🙏

[@haripriya8034]

excellent explanation

[@animeshmaru16]

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

[@nileshsinha7869]

Gonna complete the series tonight

[@sangdilbiswal30]

Hell yeah

[@Rider12374]

class Solution { public: bool isPossible(int a,int b) { //code here return abs(a-b)==1; } };

[@priyanshkumar17]

thanks for awesome explanation striver bhaiya :)

[@Zombyyieeeeee]

the best teacher

[@pratikmhatre4815]

Very helpful

[@apmotivationakashparmar722]

Thank you so much!

[@DeadPoolx1712]

UNDERSTOOD;

[@shauryatomer1058]

thanks for the great content

[@Learnprogramming-q7f]

Thank you Bhaiya

[@atharvakulkarni2024]

Excellent Explanation!!!

[@judgebot7353]

thanks

[@Yash-uk8ib]

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??

[@sparshsharma6068]

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-uk8ib]

@@sparshsharma6068 i think u have got a point!! Agreed!! Thanks for ur kind reply.

[@sparshsharma6068]

@@Yash-uk8ib Happy to help😊

[@vibhu613]

@@sparshsharma6068 great Explaination

[@sparshsharma6068]

@@vibhu613 Thanks😄

[@avanishmaurya2034]

Nice

[@hitheshpk6030]

Understood

[@KartikeyTT]

tysm sir

[@ANURAGSINGH-nl2ll]

Understand

[@anshulbhardwaj2666]

i best understood the concept from your videos sir thank you

[@poojabennabhaktula4883]

Kudos to your effort!

[@vivekreddy820]

understood sir

[@harshitjaiswal9439]

understood

[@sysfailureexe6038]

Thanks u

[@cinime]

Understood! Such an amazing explanation as always, thank you very much!!

[@UjjawalSaran]

🔥

[@parthsalat]

Understood kaka

[@amitswami3139]

Very Good content striver

[@momilijaz271]

great tip!

[@editorera239]

Thanks bro for prior explanation

[@UECAshutoshKumar]

Thank you sir

[@tanyagupta4247]

understood!

[@SatyamEdits]

Hi Tanya ...!! Nice to see you ...again...!!! if you remember.....😅

[@D44Aishwarya]

you are just amazing sir

[@tanishsharma5440]

Excellent Bro, perfect

[@lavanyaprakashjampana933]

we love your content and we love you.....🖤

[@alesblaze4745]

thanks mate!

[@pawankumarpandit1822]

thank you striver bhaiya

[@srivatsa1193]

this is awesome !

[@mriduljain1981]

completed lecture 33 of free ka tree series.

[@shivangisrivastava1158]

Amazing 👏👏

[@DilpreetSingh-cs7yz]

why the inorder traversal along with any one of the remaining two traversals gives a unique binary tree and why not any other combination??

[@priyanshkumar17]

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.

[@cricketjanoon]

Undersstod! 👍

[@vagabondfoodie5788]

Done till now 🥺🥺🥺 thankyou striver ❣️❣️

[@Sumeet_100]

Keep making this videos bhaiya

[@Professor-du2pf]

"US"

[@nagavedareddy5891]

Huge respect ❤👏

[@Anonymous-uj3jx]

Thanks :)

[@bhaveshkumar6842]

Thank you bro!!

[@BG-lj6fw]

understood.

[@jaiminsolanki5478]

Understood!

[@utkarshsharma6650]

understoooood

[@naman_goyal]

Best content brother

[@pratikshadhole6694]

understood

[@dreamyme543]

Understood:)

[@sujan_kumar_mitra]

Understood

[@Ayush-lq3fz]

understood :)))

[@ajayypalsingh]

💚

[@SibiRanganathL]

Comments

[@harshit8525]

Striver Bhaiya zindabad!!!

[@stevefox2318]

Bawaal🔥💪

[@shreyasvishwakarma8979]

noice video

[@peddikarthik7832]

what if all the nodes have same value then answer wont be unique

[@suvanshmahajan5902]

"us"

[@piyushacharya7696]

reach++

[@09_himanshusingh44]

Wow waiting for this 👍

[@KaushikSharma-c3q]

................

[@DoCTeRSinS]

boooooooooooooooooooooooooooooooooooooooom

[@yashgupta-fk3zc]

first :)

[@ojasdighe991]

🔺🔺

[@adityapandey23]

Understood

[@abhinanda7049]

understood

[@abdulrazzak2934]

understood!

[@rishabhgupta9846]

understood

[@aftabalam7103]

Understood

[@manojnavinjamuri5867]

understood

[@roopeshn3301]

Understood

[@chinu_.16]

understood

[@VikasGupta-ok9lh]

Understood