L34. Construct a Binary Tree from Preorder and Inorder Traversal | C++ | Java

[@takeUforward]

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

[@meme_eternity]

Relevel pe login otp nhi receive ho rahi..... fix it

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

[@SchrodingerMan]

@@herculean6748 welcome 💪

[@AnkitKumarGupta03]

Thank you bro.

[@anshulkumarneekhara9377]

Thanks man

[@misterbean6674]

saved my life.

[@roushankumar7684]

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

[@shubhamkumar-hx1fb]

bhut log mil jayenge ye tumhari fault hai....ager tum aankhen band karke khojoge to koi nhin dikhega

[@ransh-sahu]

@@shubhamkumar-hx1fb Searched the whole youtube being comfortable and understanding it very well . The consistency striver followed is unmatched and its true none is better than striver if u r targeting fang or higher . There is always a shortage of content or room for subscription. Praise striver rather than being cool lgunga ase bolunga

[@gouravkumarshaw5467]

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

[@gouravkumarshaw5467]

Great!!

[@ridamsoni1762]

@@gouravkumarshaw5467 grt

[@Stefan_2117]

Gr8

[@satyamraj2779]

grate.

[@THOSHI-cn6hg]

groot

[@samyakjain7422]

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

[@manaskhare412]

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

[@alexrcrew1975]

haha nice going at present whichtopic youaredoing

[@cur92lyone]

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

[@rushidesai2836]

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

[@NitishGautam-g1j]

Bro we need more teachers like you 😢😢😢 who actually can think from perspective of a beginner and explain step by step

[@natanshisharma8828]

If you are confused how the they are storing addresses, its during backtracking that the nodes addresses are being stored not during creation of the nodes.

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

[@roushankumar7684]

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

[@stith_pragya]

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

[@gautamkrishnan9982]

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

[@Cool96267]

Which programming language you are using?

[@mynk_rjpt]

@@Cool96267 c++

[@9-teen77]

did you complete it?

[@nilesh69420]

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

[@AppaniMadhavi]

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

[@gouravchaki7990]

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!

[@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-darshil]

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]

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

[@trojanhorse8278]

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

[@akankshasinha3352]

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

[@sourabhsharma2746]

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

[@rushidesai2836]

Yeh baat pe bhangdaa ho jae! :)

[@jotsinghbindra8317]

chki rkh kam bai🙌

[@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; } };

[@lalitgaikwad7238]

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

[@Parth.Deshpande]

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]

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

[@Star_Gazer_42]

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

[@sriharshas3889]

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

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

[@shikharsrivastava7312]

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

[@aastikofficial6100]

@@AmitSharma-nv2oj i > j condition means the range of elements in inorder from i to j thats why if i > j means there are no element so we have to return NULL ;

[@karthik-varma-1579]

Java Code:- class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { HashMap hm = new HashMap(); int n = inorder.length; for(int i=0;ipreEnd || inStart>inEnd) return null; TreeNode root = new TreeNode(preorder[preStart]); int hMap = hm.get(root.val); int numsLeft = hMap-inStart; root.left = builder(inorder,inStart,hMap-1,preorder,preStart+1,preStart+numsLeft,hm); root.right = builder(inorder,hMap+1,inEnd,preorder,preStart+numsLeft+1,preEnd,hm); return root; } }

[@26_jamkhandedattatray59]

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

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

[@agnijeetsharma]

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

[@sri199]

For duplicates value try dict of list to store all index of the element and pop the first one res = [] mmap = defaultdict(list) n = len(preorder) def build(preStart,preEnd,inStart,inEnd): if preStart > preEnd or inStart > inEnd: return None root = TreeNode(preorder[preStart]) orders = mmap[root.val] index = orders.pop(0) inRoot = index numsLeft = inRoot - inStart root.left = build(preStart+1,preStart+numsLeft,inStart,inRoot-1) root.right = build(preStart+numsLeft+1,preEnd,inRoot + 1,inEnd) return root for i in range(len(inorder)): mmap[inorder[i]].append(i) return build(0,n-1,0,n-1)

[@shivamchaudhary3646]

Very well explained... but at leetcode it will give memory limit exceed for a particular testcase make map globally !

[@apmotivationakashparmar722]

Thank you So much Striver !

[@vinayrohitreddypadala2705]

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.

[@KandulaAsrith]

someone please reply how to solve if the tree contain duplicate elements...

[@aastikofficial6100]

@@KandulaAsrith see in case of duplicates suppose map has two elements suppose 2 at index 0 and 4 respectively. therefore when you hash the element with index it will override the older one means in map it is stored like this 2 -> 4 only but 2 is on 0 index too. That's why for duplicates it will fail so one solution is that you can do a linear search every time in the range of inorderStart or inorderEnd ..... this will definitely gonna work but if u want more optimisation you can check using queue solution on google you will find . Hope it helps 😊

[@Lalit_Shirsath]

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

[@takeUforward]

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

[@Lalit_Shirsath]

@@takeUforward ha bhaiya 😁🤗

[@shivammishrasvnit5456]

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

[@shivammishrasvnit5456]

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

[@hiddenguy7174]

@@shivammishrasvnit5456 try passing map by reference

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

[@samarthvarshney512]

just use a unordered_map> mp

[@roushankumar7684]

Thankyou bhaiya for lifting me up❤.

[@KeigoEdits]

I am shocked, that i came up with the solution to this problem in my first attempt, though runtime was low as i was searching index of root in inorder using linear search(though dividing the space in half after each recursive call) but its still O(n). Later saw in this video, that we can use hashmap for this purpose. Though indeed I couldn't have done without the intuition I got in earlier video of striver explaining unique binary question.

[@gandhijainamgunvantkumar6783]

Thank you so much for explaining very beautifully

[@sanchitsanyam7359]

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

[@akashverma5756]

This is one of insanely tricky problem of Binary Tree.

[@iamnottech8918]

Superb explanation.

[@vishalgowrav]

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

[@vaalarivan_p]

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

[@sammy_yo5967]

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; } };

[@cinime]

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

[@MJBZG]

understood striver, much love

[@adrashsingh4109]

great explanation! Thank you

[@PratikShah123]

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

[@jayashishchoudhury9241]

Why can’t we take inRoot as the end index for preorder for the left subtree and inRoot +1 as the start index for preorder for the right sub tree?

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

[@prashukjain8519]

saved my time

[@RoneyMoon]

by the way that thing u should avoid while solving it in interview he wont be happy

[@iamnottech8918]

What an explanation !!

[@subhasishdas3011]

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

[@prayagdesai4884]

Very clear and concise explaination..

[@VivekKumar-zo7kr]

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]

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]

@@ayushjain7130 Understood.. Thanks a lot 🔥

[@rajatbansal6059]

@@ayushjain7130 ohh thanks man .

[@krishnarajs8012]

@@ayushjain7130 great... ya

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

[@adithyaas7735]

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

[@santanu29]

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

[@adithyaas7735]

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

[@sparshsharma6068]

Understood! but, Bhaiya There is a more optimal version available in Leetcode discussion.

[@takeUforward]

I don’t think so.. can you please paste it here.

[@sparshsharma6068]

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

[@siddharthmagadum16]

Your explanation is OP.

[@divakar4339]

Loved the concept. Thank You striver

[@viditaagrawal4169]

Nice explanation !! For duplicate values instead of using map we can create individual function findIndex from inorder array using visited array , which won't repeat index , my code passed on gfg

[@nikhilsachan_cse7144]

In question, it is written that no duplicate values are allowed, otherwise it will be impossible to create tree from traversals in some cases.

[@fine2981]

can u pls share ur code.??

[@viditaagrawal4169]

@@fine2981 int findIndex(int in[],int ele,int n,vector &vis){ for(int i=0;ipreEnd || inStart>inEnd) return NULL; Node* root = new Node(pre[preStart]); int index = findIndex(in,root->data,n,vis); int inleftEnd = index-1; int preleftEnd = preStart+index-inStart; root->left = solve(in,pre,inStart,inleftEnd,preStart+1,preleftEnd,vis,n); int inrightSt = index+1; int prerightSt = preleftEnd+1; root->right = solve(in,pre,inrightSt,inEnd,prerightSt,preEnd,vis,n); return root; } public: Node* buildTree(int in[],int pre[], int n) { vector vis(n,0); return solve(in,pre,0,n-1,0,n-1,vis,n); }

[@viditaagrawal4169]

@@nikhilsachan_cse7144 Its on leetcode that duplicate isn't there but on gfg its mentioned in question that duplicates are also present

[@fine2981]

/*Complete the code here. Node is as follows: struct Node { int data; Node* left; Node* right; }; */ class Solution{ public: Node* tree(int in[],int pre[], int &preindex,int ins,int ine,int n){ if(ins>ine || preindex>=n){ return NULL; } int element=pre[preindex++]; Node* root=new Node(element); int inorderindex=0; for(int i=0;idata==in[i]){ inorderindex=i; break; } } root->left=tree(in,pre,preindex,ins,inorderindex-1,n); root->right=tree(in,pre,preindex,inorderindex+1,ine,n); return root; } Node* buildTree(int in[],int pre[],int n) { int preindex=0; Node* ans=tree(in,pre,preindex,0,n-1,n); return ans; } }; can you tell me whats wrong with this code? its giving me wrong ans after 54 test cases.. this was the test case that it did not passed. 7 7 3 11 1 17 3 18 1 3 7 11 3 17 18

[@bhargavijethva7958]

Amazing!👏👏

[@prernagupta7729]

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

[@sanjai_rs7]

Brilliant idea!

[@shreyasnagabhushan4918]

this was excellent bro, topic perfectly settled in my mind

[@andrewcenteno3462]

Phenomenal explanation

[@arnedits6335]

grest explanantion.

[@siddharthsaxena6495]

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]

Because map is passed by reference.

[@arijitdas4560]

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

[@sarthak._v_]

Best Lecture

[@varnitgupta706]

amazing work

[@nextnotification9857]

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

[@aastikofficial6100]

instead you can pass map by refrence buddy .....global variables are also fine but generally that may be not a good practice

[@harshadatrimukhe9147]

TLE for last test case(Leetcode)

[@AashimaKatoch]

@Sidak Chuchra it helped thankyou

[@akashbhoyar7403]

leetcode added some crazy test case......to which striver sir's code is showing TLE. If anyone knows abt -> How to deal with TLE....Please Comment !

[@als_venky7057]

just send your map as a reference instead of sending it normally. And see the magic, boooom💥💥

[@ranjulsingh9466]

c++ code is showing memory limit exceeded .how to deal with it?

[@anujrathore5726]

same with me 202 /203 test case passed but not 1 🙃

[@iamsuryakant]

Awesome Explanation 👌

[@soubhikghosh6564]

Best solution ever!

[@yashgoyal9942]

Getting TLE on GFG and leetcode after submitting the C++ code

[@takeUforward]

Let me check this, they updated the test cases most probably.

[@kshitijvarshney1133]

@@takeUforward jst pass the map by reference

[@VivekKumar-zo7kr]

@@kshitijvarshney1133 What does this passing by reference does? We are not changing anything in map.we are just accessing..so why passing by reference passed all cases?

[@prantikofficial]

Just pass the map by reference.

[@JohnWick-kh7ow]

Why solution with unordered_map is taking more runtime than map?

[@usmanganimakandar9293]

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

[@auroshisray9140]

Loving your explanation bhaiya😍

[@bhargavnagacharan1899]

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]

Yeah updated the code..

[@bhargavnagacharan1899]

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

[@stephen9726]

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.

[@kuldeepmishra4718]

Maza aa gaya bhai. Aaise hi padhate raho

[@dsa.aditya]

IN GFG THE CODE MIGHT GET SEGMENTATION FAULT SO PLEASE USE QUEUE DATA STRUCTURE TO STORE THE MULTIPLE INDEX OF A SAME ELEMENT. REALLY Thank You so much Striver Bhaiya🙏 HERE IS THE CODE ------ Node* ans(int pre[],int preStart,int preEnd,int in[],int inStart,int inEnd,unordered_map& mp) { if (preStart > preEnd || inStart > inEnd) { return NULL; } Node* root=new Node(pre[preStart]); int inroot=mp[root->data].front(); mp[root->data].pop(); int left=inroot-inStart; root->left=ans(pre,preStart+1,preStart+left,in,inStart,inroot-1,mp); root->right=ans(pre,preStart+left+1,preEnd,in,inroot+1,inEnd,mp); return root; } Node* buildTree(int in[], int pre[], int n) { unordered_map mp; for (int i = 0; i < n; i++) { mp[in[i]].push(i); } Node* root=ans(pre,0,n-1,in,0,n-1,mp); return root; }

[@relaxingnaturalvibrations1171]

thanks bro

[@mohanseditz]

Good Explanation of code!

[@dharanit3918]

Excellent explanation bro❤❤

[@bhaveshkumar6842]

Thank you, Striver!!!

[@tushar7305]

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

[@Ak-kc7qp]

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)

[@NMCSMROHANHEGDE]

last TC in LC will work ,if you pass map by reference

[@takeUforward]

Done.

[@madhavaprashath1453]

Reason??

[@yashjain1492]

but why?

[@takeUforward]

Since it creates a copy everytime, which tends to take more time. As a new copy gets created every time..

[@yashjain1492]

@@takeUforward thanks

[@gouravkumarshaw5467]

great explanation thanks!!

[@watchlistsclips3196]

Why did u use map instead of unordered_map??

[@sahilkachhap4949]

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

[@anonymous090]

Thank you Bhaiya❤

[@digvijay1228]

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.

[@soumyodeepdey5237]

i dont think the code would work for cases where there may be repeated elements. Need to use a different data structurelike queue. Also the map needs to be passed 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.

[@aditya14-02]

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

[@prathamchoudhary]

best explanation ever

[@symbol767]

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

[@kipa_chu]

Maths = CS lol

[@enigma368]

@@kipa_chu 🤣😂

[@tankuharshida2855]

I wrote the same code in python it's showing max recursion depth exceeded

[@piyushacharya7696]

I guess you made a mistake while passing the parameter in the function, hence the base case is not executing.

[@Rahul-ls4ju]

My Logic was almost same but when I submitted on Leetcode, it was accepted but took a lot of Time(only better than 5-6%) . That is why I doubted that is it most optimized soln or not

[@takeUforward]

kzbin.infoUOgKdjeniAE

[@mridulsharma1863]

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