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

for those who are getting TLE - pass the map in function with refernce ..................... it happens beacause when we pass map without refernce it start to copy all the value........ whereas if we pass the reference it only take base address................. so saving the time :-)

@herculean6748

Жыл бұрын

Thanks man!!! I couldn't find why it was giving TLE

@SchrodingerMan

Жыл бұрын

@@herculean6748 welcome 💪

@AnkitKumarGupta03

Жыл бұрын

Thank you bro.

@anshulkumarneekhara9377

4 ай бұрын

Thanks man

Free me Aisa explanation koi nii dega. You are real life hero.

(a) Inorder (Left, Root, Right) : (b) Preorder (Root, Left, Right) : (c) Postorder (Left, Right, Root) :

@gouravkumarshaw5467

Жыл бұрын

Great!!

@ridamsoni1762

Жыл бұрын

@@gouravkumarshaw5467 grt

@Stefan_2117

22 күн бұрын

Gr8

It took a while to understand this tricky problem, but now it's completely clear. Thank you striver, kudos for such amazing content.

@alexrcrew1975

2 жыл бұрын

haha nice going at present whichtopic youaredoing

I spent two days trying to understand this Algo. Finally, your video made me understand it. Thanks. :)

@rushidesai2836

12 күн бұрын

I can understand. Two of the most important quesitons - Tree from Preorder and Inorder, and tree from inorder and postorder.

coding ninja ka course liya tha usme iski explanation smjh nhi aayi lekin apki video dekhi aur 1 shot me smjh aagai . thanks striver . u teach like u r my friend and not a teacher which i like most bout ur videos !!

Thankyou striver 🥺 you’re a gem that all of us have got !!

Thank you so much for explaining very beautifully

You have changed the teachers image as spreading skill without taking any money❤

Understood! So awesome explanation as always, thank you very much!!

Very clear and concise explaination..

Here is the code to deal with duplicate elements we use a queue so that the element that occurs later in the in-order get pushed at the front and keep popping the index that are processed, we now get a correct tree formed according to the preorder traversal class Solution{ public: Node* solve(int in[],int in_start,int in_end,int pre[],int pre_start,int pre_end,map &pos) { if(pre_start>pre_end|| in_start>in_end) { return NULL; } int inroot=pos[pre[pre_start]].front(); pos[pre[pre_start]].pop(); int elem=inroot-in_start; Node* root=new Node(pre[pre_start]); root->left=solve(in,in_start,inroot-1,pre,pre_start+1,pre_start+elem,pos); root->right=solve(in,inroot+1,in_end,pre,pre_start+elem+1,pre_end,pos); return root; } Node* buildTree(int in[],int pre[], int n) { // Code here if(n==0) return NULL; map pos; for(int i=0;i

@meetmandhane

Жыл бұрын

Will the time complexity of this approach remain same i.e. O(N)?

@ayushgautam169

Жыл бұрын

yeah exactly what i did i took a list and removed from front, like we can take a queue

@i-am-darshil

8 ай бұрын

Is a unique tree even possible in case of duplicate elements? 2 trees can be formed with the same inorder and preorder Inorder - 1 2 2 3 2 Preorder - 2 2 1 2 3

@tanishq2766

7 ай бұрын

I guess we don’t need a map, if we can split them as we can always split into two parts.

@trojanhorse8278

9 күн бұрын

@@i-am-darshil Correct, You can't always construct a unique binary tree when the keys are repeated. EX is Pre : 10 10 10 In : 10 10 10 , now based on your choice of root in in-order you will get different tree structures. Hence only if the interviewer wants to check whether you know this fact or not he might ask this question but once you explain to him that we can't always create a unique tree without defining the rule to choose the root from in-order, he mostly will get satisfied and won't ask you to actually write a code.

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

Great explanation as always. The last dry run just before showing code was very very helpful.

THE BEST TREE series even though i have taken a paid course...still i am coming here to understand ...>God Bless u TUF

Loved the concept. Thank You striver

Thanks alot bhai!!. I didn't understood first but in other problems I need to use this, so I visited once again and now its clear cut for me thanks alot..

Hey Striver, this algorithm is working for unique values but not for the repeated ones. Example:- inorder = [7 ,3 ,11 ,1 ,17 ,3 ,18] postorder = [1, 3, 7, 11, 3, 17, 18] And In this scenario i dont think inMap is kind of working.

Keep Going Striver!! I am following your SDE Sheet to revise on the DSA concepts. Thank you so much for all your content.

@Cool96267

2 жыл бұрын

Which programming language you are using?

@mynk_rjpt

2 жыл бұрын

@@Cool96267 c++

@9-teen77

2 жыл бұрын

did you complete it?

What an explanation!!🥺❤ Take a bow striver🙇‍♂️

This code doesn't work for duplicate values, gfg has updated their testcases.

@rushidesai2836

Жыл бұрын

Khud se try karna bhai, he is already putting out so much content for us.

Awesome Explanation 👌

this was excellent bro, topic perfectly settled in my mind

For interviewbit solution , pass the map by reference TreeNode* buildT(vector &A,int prestart,int preend,vector &B,int instart,int inend , map& mp){ if(prestart>preend || instart>inend){ return NULL; } TreeNode* root = new TreeNode(A[prestart]); int inroot = mp[root->val]; int leftnums = inroot - instart; root->left = buildT(A,prestart+1,prestart+leftnums,B,instart,inroot-1,mp); root->right = buildT(A,prestart+leftnums+1,preend,B,inroot+1,inend,mp); return root; } TreeNode* Solution::buildTree(vector &A, vector &B) { map mp; for(int i=0;i

@priyanshurai460

2 жыл бұрын

Can you please tell me why the time limit exceeds when the map is passed by value?

@gay-bitchass-nigga3036

Жыл бұрын

@@priyanshurai460 coz everytime the function gets called it creates a new map with same name at another memory location with same values. So these operations take time and space which is alot, thats why TLE.

great explanation thanks!!

You are doing a great job bro...thanks a lot.

Brilliant Explanation

Brilliant idea!

This is toh another level explanation bhai. 👌👌 how can someone be so clear in his explanation.. btw amazing thanks bhai. love from punjab

@rushidesai2836

12 күн бұрын

Yeh baat pe bhangdaa ho jae! :)

@jotsinghbindra8317

2 күн бұрын

chki rkh kam bai🙌

great explanation! Thank you

Thankyou bhaiya for lifting me up❤.

Hi striver love from iit r. I just wanna clarify that if case the in order traversal have duplicate values then what should be our approach

@samarthvarshney512

Жыл бұрын

just use a unordered_map> mp

Loving your explanation bhaiya😍

amazing work

Phenomenal explanation

You're The Real Life G.O.A.T i.e Greatest of All Times

Thanks allot Bhaiya ,your videos awesome , I love your videos.

Superb Explanation ! Here in the code we should pass the map as reference otherwise we will get the memory limit exceeded.

Your explanation is OP.

Amazing!👏👏

understood ,nice explanation.What if duplicates values are present?

Thank you, Striver!!!

Out of all these coding I would just provide method to prepare Biriyani!! Step 1 Prepare saffron-kewra water and chop veggies To make a delightful chicken biryani dish, firstly soak saffron in water to prepare saffron water (one tsp saffron can be soaked in 1/4 cup water). Next, mix kewra drops in water and mix well to make kewra water. Set them aside for later usage. Now, chop the onion and coriander leaves and keep them aside. Step 2 Saute the onions Meanwhile, heat olive oil in a deep bottomed pan. Once the oil is hot enough, add cumin seeds, bay leaf, green cardamom, black cardamom, cloves in it, and saute for about a minute. Then, add chopped onion to it and saute until pink. Now, add chicken into it with slit green chillies, turmeric, salt to taste, ginger-garlic paste, red chilli powder and green chilli paste. Mix well all the spices and cook for 2-3 minutes. Then, add hung curd into it and give a mix. (Make sure the chicken is washed properly and patted dry before adding it to the dish) Step 3 Cook biryani on low heat for 5-6 minutes Turn the flame to medium again and add garam masala in it along with ginger julienned, coriander and mint leaves. Add kewra water, rose water and 1 tsp saffron water in it. Cook till the chicken is tender. Then add 1 cup cooked rice and spread evenly. Then add the remaining saffron water and pour ghee over it. You can now cook the dish without the lid or cover it with a lid to give a dum-effect due to the steam formation. Step 4 Serve hot chicken biryani with your favourite chutney or raita Cook for 15-20 minutes with a closed lid and garnish with 1 tbsp fried onions and coriander leaves. Serve hot chicken biryani with raita of your choice. Enjoy!

map mp giving runtime error; we need to take maps mp; ig

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ /* JUST FINDING THE POSITION OF THE FIRST ELEMENT IN THE PREORDER VECTOR IN THE INORDER VECTOR THEN USING THE POSITION OF THAT ELEMENT TO FIND THE LEFT SUBTREE AND THE RIGHT SUBTREE */ class Solution { public: int find_pos(vectorv,int x){ for(int i=0;ileft=buildTree(l1,l2); root->right=buildTree(r1,r2); return root; } };

Loved your content :)

Iterative approach seems to be difficult...Can u explain that too?

Why are we passing inorder array when we are not using it anywhere in buildtree function ??

Best solution ever!

Well explained

doing dry run is little bit difficult pr when i understood 😌 toh bas mazza agaya😀. Thnx bro for such great video 😊

Why did u use map instead of unordered_map??

Thank you Bhaiya

We are using map so I think the time complexity should be O( NlogN ) ?

Huge respect...❤👏

grest explanantion.

I don't think there is any need of passing inorder vector there. I assume its just there for better code readability. Please correct me if I am wrong

Correct me if I'm wrong but doesn't it only work with a Complete Binary Tree. I'm mean the resultant is a CBT.

simplified version of code explained above /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode* constructTree(int i,int j,int &ind,vector &preorder,vector &inorder,unordered_map &mp) { if(i>j) { return NULL; } int rootVal=preorder[ind]; ind+=1; TreeNode *root=new TreeNode(rootVal); int in=mp[rootVal]; root->left=constructTree(i,in-1,ind,preorder,inorder,mp); root->right=constructTree(in+1,j,ind,preorder,inorder,mp); return root; } TreeNode* buildTree(vector& preorder, vector& inorder) { unordered_map mp; for(int i=0;i

@AmitSharma-nv2oj

Жыл бұрын

can you explain how i>j condition works

can we use unordered map to save time complexity ? map --> O( log n ) unordered_map --> O(1)

@takeUforward

2 жыл бұрын

Unordered map’s worst case is still o(n) 😉

@Lalit_Shirsath

2 жыл бұрын

@@takeUforward ha bhaiya 😁🤗

@shivammishrasvnit5456

2 жыл бұрын

@@takeUforward bhyaa still in leetcode tle coming what to do😞😞 ?

@shivammishrasvnit5456

2 жыл бұрын

no i got accepted after putting map by reference, thanks for it you explained soo well!

@hiddenguy7174

2 жыл бұрын

@@shivammishrasvnit5456 try passing map by reference

best explanation ever

Bhaiya aapne video me map ko call by reference se pass nai kiye so TLE aa raha he ..bt aapka description ke code me wahi he ....(just a simple '&'missing from the map of construct tree function)

Good Explanation of code!

Thank you sir

Excellent explanation bro❤❤

Why does passing the map by reference works? We are not changing anything in map.we are just accessing..so why passing by reference passed all cases?

@ayushjain7130

2 жыл бұрын

According to me. If we pass by value, the compiler have to create a new map and copy the existing map's values into it. So it will take extra time to create a new map, while in pass by reference you are just passing the address of a memory location

@VivekKumar-zo7kr

2 жыл бұрын

@@ayushjain7130 Understood.. Thanks a lot 🔥

@rajatbansal6059

2 жыл бұрын

@@ayushjain7130 ohh thanks man .

@krishnarajs8012

2 жыл бұрын

@@ayushjain7130 great... ya

Gazab! Thanks Striver

Thanks a lot Striver for providing such amazing content to us for free of cost...respect for your Hard Work. Just one doubt , not sure if leetcode has updated its tcs coz now this algo is giving TLE at 202nd tc out of 203 tcs...

@013_aman

Жыл бұрын

Take map as by reference it will work

@SahilSharma-to8nd

Жыл бұрын

@@013_aman thanks

Vro dus video dekhi but nhi hua apki video ka sirf first two minutes ke logic ko dekh kar samjh gya and done it🙃🙃

what if we have duplicates ?? then what changes we need to do?

i have small doubt, why map is not passed by reference?? usually we pass vector by reference right but map is also from stl library, can u pls explain this one?

@takeUforward

2 жыл бұрын

Yeah updated the code..

@bhargavnagacharan1899

2 жыл бұрын

@@takeUforward thankyou bro for the series love u ❤️

@stephen9726

2 жыл бұрын

It gave me TLE when map is not passed by reference and was stuck there since long time thinking that all the code is same. When I saw your comment, I tried passing the map by reference and got accepted. Thanks for the comment.

Thanks a lot striver for the amazing content. Solved it myself after watching the explanation. One more thing is that I think there is no need of preEnd because we can check whether there is any node left or not using inStart and inEnd and preStart is only needed to get the new root. Am I correct?

@user-oh7fv6mm6s

11 ай бұрын

yes this was my exact doubt, why is pre end needed to be checked to return null, because that can be done by instart and inend itself

@chandrachurmukherjeejucse5816

11 ай бұрын

@@user-oh7fv6mm6s yes. But moving forward you will find that there is a similar problem where all of them are required. May be to maintain similarity he has taken that also.

@user-oh7fv6mm6s

11 ай бұрын

@@chandrachurmukherjeejucse5816 ohh okay, haven't faced such a problem yet, thanks :)

in base case no need to check both in and pre any 1 check is enough

wrote the code in first attempt😀, i have made the map global to the class and thus no need to pass it again and again

202/203 test case timelimit exceeded to fix this just put ''&map" on function arguments

@santanu29

2 жыл бұрын

Thank you. I was stuck there. Quickly can you mention why it gives tle for not using "&"

@adithyaas7735

2 жыл бұрын

@@santanu29'&' means we are passing the map as reference (only the address of it) In pass by reference, no new copy of the variable is made, so overhead of copying is saved

Maza aa gaya bhai. Aaise hi padhate raho

Wonderful !! Btw, what if Tree contains duplicate values, where finding index out of InOrder will be a challenge..!

Awesome vid!!!

how to do it iteratively ?

do we really need of preStart and preEnd ? can anyone please explain ?

@chiraggill2940

27 күн бұрын

no only a single index variable will also work

inoder should be in increasing order na?

Understood thanks :)

This code is same as striver's code but still it is not giving tle and striver's code is giving tle, can anyone explain why?? TreeNode* help(vector&pre, int preS, int preE, vector&in, int inS, int inE, map& m) { if(preS>preE or inS>inE) return NULL; TreeNode* curr = new TreeNode(pre[preS]); int pos = m[curr->val]; int len = pos-inS; curr->left = help(pre, preS+1, preS+len, in, inS, pos-1, m); curr->right = help(pre, preS+len+1, preE, in, pos+1, inE, m); return curr; } TreeNode* buildTree(vector& preorder, vector& inorder) { mapm; for(int i=0;i

@JohnWick-kh7ow

2 жыл бұрын

Because map is passed by reference.

@arijitdas4560

2 жыл бұрын

you passed the map as this "&m".....that's why.I had the same doubt but then I noticed

Do check out the code link provided in the description to avoid TLE on leetcode.

@varshiniramesh3752

2 жыл бұрын

Yeah! I got it as well. It's the same code. But, why isn't mine working?

@prajaktakeer487

2 жыл бұрын

what is the change?

@prajaktakeer487

2 жыл бұрын

got it, just pass the vectors and map by reference

You explained well bro but while explaning code pls zoom it so that we don't have strain in eyes

Well can someone explain why is the name of the functions same (buildtree) it’s causing confusion

tysm sir

note :In case of duplicates map won't work.because it overwrites old index with latest index. so do linear search within the bounds in inStart and inEnd.

what about the duplicate elements ?

I hate Math so much, figuring out how to calculate where these pointers should be is such a headache

@kipa_chu

2 жыл бұрын

Maths = CS lol

@enigma368

Жыл бұрын

@@kipa_chu 🤣😂

Why is map is used can't we find the element from the inorder vector that is given initially

how did u derive the base condition??

thanks mate!

bro the C++ code is not working for the last TC(203th) on LC...please have a look

@takeUforward

2 жыл бұрын

All codes are tested.

@prateekjoshi6425

2 жыл бұрын

@@takeUforward just copied your github code for C++....still the same issue

@kshitijvarshney1133

2 жыл бұрын

@@prateekjoshi6425 jst pass the map by reference

@SHASHANKRUSTAGII

2 жыл бұрын

@@prateekjoshi6425 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode* buildTree(vector& preorder, vector& inorder) { map m; for(int i=0;ipreend or instart>inend) return nullptr; TreeNode* root = new TreeNode(preorder[prestart]); int inroot = m[root->val]; int numsleft = inroot-instart; root->left = buildTree(preorder, prestart+1,prestart+numsleft, inorder, instart, inroot-1, m); root->right = buildTree(preorder, prestart+numsleft+1,preend, inorder, inroot+1,inend, m) ; return root; } };

3:30 - 3:35 CW : 12:40 - 17:01

Thank you Bhaiya❤

Love this vid. ❤

can anybody explain why passing map not by reference gives tle

How the node will connect to the node->left or right??

@piyushacharya7696

Жыл бұрын

When returning, do dry run once and you will get it.