Please likeeee, shareeee and subscribeeeeeeee :) Also follow me at Insta: Striver_79
@SchrodingerMan Жыл бұрын
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
Free me Aisa explanation koi nii dega. You are real life hero.
@manaskhare4122 жыл бұрын
It took a while to understand this tricky problem, but now it's completely clear. Thank you striver, kudos for such amazing content.
@alexrcrew19752 жыл бұрын
haha nice going at present whichtopic youaredoing
@samyakjain74222 жыл бұрын
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 !!
@cur92lyone2 жыл бұрын
I spent two days trying to understand this Algo. Finally, your video made me understand it. Thanks. :)
@rushidesai283618 күн бұрын
I can understand. Two of the most important quesitons - Tree from Preorder and Inorder, and tree from inorder and postorder.
@akankshasinha33522 жыл бұрын
Thankyou striver 🥺 you’re a gem that all of us have got !!
@nilesh694203 ай бұрын
Great explanation as always. The last dry run just before showing code was very very helpful.
@cinime Жыл бұрын
Understood! So awesome explanation as always, thank you very much!!
@stith_pragya8 ай бұрын
UNDERSTOOD...Thank You So Much for this wonderful video...........🙏🙏🙏
@AppaniMadhavi3 ай бұрын
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..
@gandhijainamgunvantkumar67832 жыл бұрын
Thank you so much for explaining very beautifully
@roushankumar76845 ай бұрын
You have changed the teachers image as spreading skill without taking any money❤
@ShreyaJain-1808 Жыл бұрын
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-darshil8 ай бұрын
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
@tanishq27668 ай бұрын
I guess we don’t need a map, if we can split them as we can always split into two parts.
@trojanhorse827815 күн бұрын
@@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.
@prayagdesai48842 жыл бұрын
Very clear and concise explaination..
@ss-pz4zh Жыл бұрын
THE BEST TREE series even though i have taken a paid course...still i am coming here to understand ...>God Bless u TUF
@gautamkrishnan99822 жыл бұрын
Keep Going Striver!! I am following your SDE Sheet to revise on the DSA concepts. Thank you so much for all your content.
@Cool962672 жыл бұрын
Which programming language you are using?
@mynk_rjpt2 жыл бұрын
@@Cool96267 c++
@9-teen772 жыл бұрын
did you complete it?
@divakar43392 жыл бұрын
Loved the concept. Thank You striver
@Parth.Deshpande2 жыл бұрын
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
@priyanshurai4602 жыл бұрын
Can you please tell me why the time limit exceeds when the map is passed by value?
@gay-bitchass-nigga30362 жыл бұрын
@@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.
@vishalgowrav Жыл бұрын
What an explanation!!🥺❤ Take a bow striver🙇♂️
@sourabhsharma2746 Жыл бұрын
This is toh another level explanation bhai. 👌👌 how can someone be so clear in his explanation.. btw amazing thanks bhai. love from punjab
@rushidesai283618 күн бұрын
Yeh baat pe bhangdaa ho jae! :)
@jotsinghbindra83178 күн бұрын
chki rkh kam bai🙌
@vinayrohitreddypadala27056 ай бұрын
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.
@iamsuryakant2 жыл бұрын
Awesome Explanation 👌
@shreyasnagabhushan4918 Жыл бұрын
this was excellent bro, topic perfectly settled in my mind
@sanchitsanyam7359Ай бұрын
Thanks allot Bhaiya ,your videos awesome , I love your videos.
@prernagupta772911 ай бұрын
You are doing a great job bro...thanks a lot.
@gouravkumarshaw54672 жыл бұрын
great explanation thanks!!
@roushankumar76845 ай бұрын
Thankyou bhaiya for lifting me up❤.
@adrashsingh41092 ай бұрын
great explanation! Thank you
@anubhav452 Жыл бұрын
/** * 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; } };
@sanjai_rs78 ай бұрын
Brilliant idea!
@neelpatel1222 жыл бұрын
Brilliant Explanation
@gouravchaki799011 ай бұрын
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!
@lalitgaikwad72384 ай бұрын
You're The Real Life G.O.A.T i.e Greatest of All Times
@iamnottech89185 күн бұрын
Superb explanation.
@varnitgupta7065 ай бұрын
amazing work
@auroshisray91402 жыл бұрын
Loving your explanation bhaiya😍
@andrewcenteno346211 ай бұрын
Phenomenal explanation
@iamnottech89185 күн бұрын
What an explanation !!
@bhargavijethva79584 ай бұрын
Amazing!👏👏
@vaalarivan_p Жыл бұрын
3:30 - 3:35 CW : 12:40 - 17:01
@user-tk2vg5jt3l3 ай бұрын
Thank you Bhaiya
@faizalam3552 жыл бұрын
Loved your content :)
@bhaveshkumar68422 жыл бұрын
Thank you, Striver!!!
@siddharthmagadum162 жыл бұрын
Your explanation is OP.
@sriharshas38894 ай бұрын
Superb Explanation ! Here in the code we should pass the map as reference otherwise we will get the memory limit exceeded.
@26_jamkhandedattatray592 жыл бұрын
doing dry run is little bit difficult pr when i understood 😌 toh bas mazza agaya😀. Thnx bro for such great video 😊
@arnedits6335Ай бұрын
grest explanantion.
@TonyStark-ct8xd Жыл бұрын
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.
@soubhikghosh6564 Жыл бұрын
Best solution ever!
@KartikeyTTАй бұрын
tysm sir
@GoluYadav-cg3kx Жыл бұрын
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
here is simple version of code class Solution { public: TreeNode* build(vector& preorder, vector& inorder, int& preStart, int inStart, int inEnd,unordered_map&mp) { if (inStart > inEnd) return nullptr; TreeNode* curr = new TreeNode(preorder[preStart]); int pos=mp[preorder[preStart]]; preStart++; // Move to the next root in the preorder sequence curr->left = build(preorder, inorder, preStart, inStart, pos - 1,mp); curr->right = build(preorder, inorder, preStart, pos + 1, inEnd,mp); return curr; } TreeNode* buildTree(vector& preorder, vector& inorder) { unordered_mapmp; for(int i=0;i
@dharanit39182 жыл бұрын
Excellent explanation bro❤❤
@prathamchoudhary2 жыл бұрын
best explanation ever
@clarencegomes60762 жыл бұрын
Gazab! Thanks Striver
@003_sambit5 Жыл бұрын
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
@elements86302 жыл бұрын
Awesome vid!!!
@adithyaas77352 жыл бұрын
202/203 test case timelimit exceeded to fix this just put ''&map" on function arguments
@santanu292 жыл бұрын
Thank you. I was stuck there. Quickly can you mention why it gives tle for not using "&"
@adithyaas77352 жыл бұрын
@@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
@kuldeepmishra47182 жыл бұрын
Maza aa gaya bhai. Aaise hi padhate raho
@Anonymous-uj3jx2 жыл бұрын
Understood thanks :)
@ankushsingh3392 Жыл бұрын
Vro dus video dekhi but nhi hua apki video ka sirf first two minutes ke logic ko dekh kar samjh gya and done it🙃🙃
@dipanshu-singh Жыл бұрын
Love this vid. ❤
@moinul69422 жыл бұрын
Do check out the code link provided in the description to avoid TLE on leetcode.
@varshiniramesh37522 жыл бұрын
Yeah! I got it as well. It's the same code. But, why isn't mine working?
@prajaktakeer4872 жыл бұрын
what is the change?
@prajaktakeer4872 жыл бұрын
got it, just pass the vectors and map by reference
@anonymous090 Жыл бұрын
Thank you Bhaiya❤
@subhasishdas30112 жыл бұрын
in base case no need to check both in and pre any 1 check is enough
@riyankadey102 Жыл бұрын
Amazing 🔥❤️
@UECAshutoshKumar11 ай бұрын
Thank you sir
@jorgereis69432 жыл бұрын
Thankyouuuuuuuuuuuuuuuuuuu, you're the man
@alesblaze4745 Жыл бұрын
thanks mate!
@sammy_yo596711 ай бұрын
C++ code to run on Leetcode: - class Solution { public: TreeNode* buildTree(vector& preorder,int preStart,int preEnd,vector& inorder,int inStart,int inEnd, map& inMp) { if(preStart > preEnd || inStart > inEnd) return NULL; TreeNode* root = new TreeNode(preorder[preStart]); int inRoot = inMp[root->val]; int numsLeft = inRoot - inStart; root ->left = buildTree(preorder,preStart+1,preStart+numsLeft,inorder,inStart,inRoot - 1,inMp); root -> right = buildTree(preorder,preStart+numsLeft+1,preEnd,inorder,inRoot+1,inEnd,inMp); return root; } TreeNode* buildTree(vector& preorder, vector& inorder) { map inMp; for(int i = 0; i < inorder.size(); i++) { inMp[inorder[i]] = i; } TreeNode* root = buildTree(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1,inMp); return root; } };
@nextnotification98573 ай бұрын
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
@shivamchaudhary364611 ай бұрын
Very well explained... but at leetcode it will give memory limit exceed for a particular testcase make map globally !
@Lalit_Shirsath2 жыл бұрын
can we use unordered map to save time complexity ? map --> O( log n ) unordered_map --> O(1)
@takeUforward2 жыл бұрын
Unordered map’s worst case is still o(n) 😉
@Lalit_Shirsath2 жыл бұрын
@@takeUforward ha bhaiya 😁🤗
@shivammishrasvnit54562 жыл бұрын
@@takeUforward bhyaa still in leetcode tle coming what to do😞😞 ?
@shivammishrasvnit54562 жыл бұрын
no i got accepted after putting map by reference, thanks for it you explained soo well!
@hiddenguy71742 жыл бұрын
@@shivammishrasvnit5456 try passing map by reference
@achalsayee2534Ай бұрын
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.
@PratikShah1234 ай бұрын
Wonderful !! Btw, what if Tree contains duplicate values, where finding index out of InOrder will be a challenge..!
@Saurav_suman-pj8uk Жыл бұрын
loving your video
@ankitsingh91472 жыл бұрын
Thankyou Bhaiya😀
@deepaksarvepalli23442 жыл бұрын
You are doing a great work
@rishabhgupta9846 Жыл бұрын
understood ,nice explanation.What if duplicates values are present?
@divyanshuyadav7278 Жыл бұрын
amazing🔥🔥🔥
@harshadatrimukhe9147 Жыл бұрын
TLE for last test case(Leetcode)
@sidakchuchra9643 Жыл бұрын
pass map by refrence\
@AashimaKatoch Жыл бұрын
@@sidakchuchra9643 it helped thankyou
@avanishmaurya20345 ай бұрын
Nice
@harshitjaiswal94394 ай бұрын
understood
@sparshsharma60682 жыл бұрын
Understood! but, Bhaiya There is a more optimal version available in Leetcode discussion.
@takeUforward2 жыл бұрын
I don’t think so.. can you please paste it here.
@sparshsharma60682 жыл бұрын
@@takeUforward Here's the java code bhaiya private TreeNode constructTree(TreeNode root, int[] idx, int stop,int[] preorder, int[] inorder){ if(idx[0] >= preorder.length) return root; if(inorder[idx[1]] == stop){ idx[1]++; return root; } root = new TreeNode(preorder[idx[0]++]); root.left = constructTree(null, idx, root.val, preorder, inorder); root.right = constructTree(null, idx, stop, preorder,inorder); return root; } public TreeNode buildTree(int[] preorder, int[] inorder) { int[] idx = {0,0}; //{preorder_idx, inorder_idx} return constructTree(null, idx, Integer.MAX_VALUE, preorder, inorder); } Time O(n), Space O(n) (recursive) I kept on dry running it and it then seemed logical, but, I still don't know the intuition behind it. It will be very helpful, If can you make a LC post and explain the intuition behind this. link to discussion : leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/discuss/34543/Simple-O(n)-without-map Look in the comments, you will find C++ or java code.
@pirangitharun87362 жыл бұрын
I like ur intro bro
@bishalpandit44642 жыл бұрын
Striver always op 🔥🔥
@chitrrakarartwork9136 Жыл бұрын
thanks bro
@vrandakansal59402 жыл бұрын
🙌🙌
@dreamyme543 Жыл бұрын
Understood:)
@sujan_kumar_mitra2 жыл бұрын
Understood
@codding32world50 Жыл бұрын
For TLE on leetcode just declare map public don't pass it in the function
@adarshpandey622 Жыл бұрын
Bro you saved my whole day
@saiprashanth2646 Жыл бұрын
Thank u so much bro.
@tejuschaturvedi6234 Жыл бұрын
you can also pass the map as reference when passing the map in function .
@prashukjain85195 ай бұрын
saved my time
@symbol7672 жыл бұрын
I hate Math so much, figuring out how to calculate where these pointers should be is such a headache