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

Striver doesn't teach us to just solve a problem. He teaches us how to think so that we will be able to solve the future problems on our own. He is an example of this proverb - "Give a man a fish and you feed him for a day. Teach a man to fish and you feed him for a lifetime." He teaches us to fish!🎣

The most important part of his teaching is to beautifully explain the approach and to build the intuition behind the solving. Thanks!!!!!!!!!!!!!!!!!!!!!1

You explained the previous question so beautifully that i didn't even need to read this question. Thanks striver!!!!

You explained the previous question so beautifully that I solved this one by myself

Best teacher !!..providing quality content for free :)

just under stand last question & now able to right the code for this one also by my own.. Excellent teaching skills.. TUF will grow more..

Grateful for these amazing videos!!

Thank you sir for the series. You are doing really a great job.

Aaj smjh aaya why this works u explained so beuatifully ki feel aagi.

Bht Achche se smjhaye aapne... Thank you...🙂

In c++, Instead of map, we can use unordered_map which will do read operation in O(1). map is used when we want keys to be sorted on insert

@ekanshsanger8356

2 жыл бұрын

In worst case unordered map will take O(N) :p

@googlepay4295

Жыл бұрын

@@ekanshsanger8356 yes but that wont matter on LC ig coz its not CF

@Ayush37262

2 ай бұрын

​@@ekanshsanger8356But still its always preferred to use unordered_map because that worst case happens 1 in a million times

I had a doubt.... Like you explain us this approaches in great detail so do we need to do this same thing in interviews too or only briefly?

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

A simpler recursive solution without map. Based on simple idea that the right segment of inorder range will constitute the right subtree and left one will constitute the left subtree. Idea is to choose wisely which recursion will be called first (in postorder, we call for right subtree first). Here's my solution with comments ;) TreeNode* getNode(vector& inor, vector& post, int s, int e, int &i) { // the inorder range is incorrect if(s > e) return NULL; // the current postorder is the root at this subtree int root = post[i--]; TreeNode *node = new TreeNode(root); // find the root element in the inorder range int ind = s; while(inor[ind] != root) ind++; // elements to the right of root in inorder seq are to the right subtree node->right = getNode(inor, post, ind+1, e, i); // elements to the left of root in inorder seq are to the left subtree node->left = getNode(inor, post, s, ind-1, i); return node; } TreeNode* buildTree(vector& inorder, vector& postorder) { int i = postorder.size()-1; // postorder index. root is at right return getNode(inorder, postorder, 0, inorder.size()-1, i); } PS: I tried this question myself and this is what I came up with!! Then after that I watched Striver's solution.

Quality Product, keep spreading knowledge , thanks Striver!

thank you VERY MUCH brilliant explanation👏

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

@rahulkumarbarik7584

2 жыл бұрын

thanks for help bro, worked for me

@knowhere6073

2 жыл бұрын

but what was the problem bro?? can u plz explain

@rahulsrivastava1040

2 жыл бұрын

@@knowhere6073 Actually it was new map again again that's why

@abhishekdhok5245

2 жыл бұрын

@@knowhere6073 When we pass anything without reference everytime new copy of that thing is created. But when we pass anything by reference only one copy is created and everytime we refer to the same copy.. That's why it is fast.

Thanks man helped me a lot!!

just solved this question by own bcz of prev lecture . thanks striver ❤❤

Before you optimize for space as you have done with the pointers it would help to have just taken a slice of the array and pass that around as a sub array.

best explanation to this problem

what if two values in the array is same, then the map won't work right? what should we do in that case?

please also cover a "construct a binary tree from levelorder and inorder Traversal".

Thank you !

great explanation

Can someone explain why "ps, ps+ri-is-1" is used in line 17 of github repo? (Java)

Very beautifully explained bhaiya

can anyone tell me that why this question gives me TLE in Leetcode Code:- /** * 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& inorder, vector& postorder) { if(inorder.size() != postorder.size()) return NULL; map mpp; for(int i = 0;ipe || is>ie) return NULL; TreeNode* root = new TreeNode(postorder[pe]); int inroot = mpp[postorder[pe]]; int numleft = inroot-is; root->left = build(inorder,is,inroot-1,postorder,ps,ps+numleft-1,mpp); root->right = build(inorder,inroot+1,ie,postorder,ps+numleft,pe-1,mpp); return root; } };

@ITACHIUCHIHA-dr8sz

Жыл бұрын

In build function make inorder, postorder, and map as reference that is make it like this, vector&inorder,.....

@laveshgoyal9974

Жыл бұрын

@@ITACHIUCHIHA-dr8sz wow, never noticed passing by ref will make such big difference

@guptashashwat

Жыл бұрын

@@laveshgoyal9974 Yes, it avoids making copies

@karunasharma9416

Жыл бұрын

@@ITACHIUCHIHA-dr8sz thanks yaar , it really helped.

@amarjeetkumarsingh733

Жыл бұрын

@@ITACHIUCHIHA-dr8sz Thanks Bro

Thats call quality content

great explanation !!

Nice explanation.

Huge respect....❤👏

Another Approach: class Solution { public: int index=0; void createHashmap(vector& inorder,unordered_map &map){ for(int i=0;ie) return NULL; node=new TreeNode(postorder[index++]); int tarIndex=map[node->val]; node->right=makeTree(node->right,postorder,tarIndex+1,e,inorder,map); node->left=makeTree(node->left,postorder,s,tarIndex-1,inorder,map); return node; } TreeNode* buildTree(vector& inorder, vector& postorder) { reverse(postorder.begin(),postorder.end()); unordered_map map; createHashmap(inorder,map); TreeNode* root=makeTree(root,postorder,0,inorder.size()-1,inorder,map); return root; } };

Great Explanation

If 2 or more elements are same in the each of the postorder or inorder traversal, then how to map. Such situation is resulting in segmentation faults. How to cover this edge case ?

why is this code showing runtime error on leetcode? /** * 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& inorder, vector& postorder) { map inmap; if(inorder.size()!=postorder.size()) return NULL; for(int i=0;ival]; int inleft=inroot-instart; t->left=maketree(inorder,instart,inroot-1, postorder,pst,pst+inleft-1, inmap ); t->right=maketree(inorder,inroot+1,inend, postorder,pend-inleft, pend-1 ,inmap ); return t; } };

bhaiya 1 number explain kiya he :) Thanks

instead of ps + numLeft - 1 shall we use inRoot - 1? for left subTree

@mukeshkuiry

Жыл бұрын

No how the element of just left of root position our left tree part

I was able to code by myself 🥳

Please try to upload all the videos till Sunday 🙏🙏

understood

Understood!

How many videos you are planning to put in this series?

thanks mate!

Understood Bhaiya!

Can anyone tell me the actual time complexity . I cant understand that

One video on topic construct binary tree from preorder and postorder please (leetcode 889)

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

@takeUforward

2 жыл бұрын

Copy my code, submit, its working, all codes are tested.

@prateekjoshi6425

2 жыл бұрын

@@takeUforward thanks...this worked...but for preorder its not working

@kwanikar7

2 жыл бұрын

@@prateekjoshi6425 try passing the map by reference

understood!!

Bhut BAdiya video he sir, hmesha ki trah

both this and the previous question will mess with your brain.

@anuj8855

16 күн бұрын

Exactly 💯

KUDOOOSSSSSS... THIS IS FIREEEE

Thank you Bhaiya

class Solution { public: TreeNode* create(vector& inorder, vector& postorder, unordered_map& hash, int is, int ie, int ps, int pe) { if(is>ie || ps>pe) return nullptr; int rootIndxInInorder=hash[postorder[pe]]; int lps=ps; int lpe=lps+rootIndxInInorder-is-1; int lis=is; int lie=rootIndxInInorder-1; int rps=lpe+1; int rpe=pe-1; int ris=rootIndxInInorder+1; int rie=ie; TreeNode* root=new TreeNode(postorder[pe]); root->left=create(inorder,postorder,hash,lis,lie,lps,lpe); root->right=create(inorder,postorder,hash,ris,rie,rps,rpe); return root; } TreeNode* buildTree(vector& inorder, vector& postorder) { int n=inorder.size(); unordered_map hash; for(int i=0;i

Thank you sir

Ahhh nice one ✌

Python Solution class Solution: def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]: hm = dict() for i in range(len(inorder)): hm[inorder[i]] = i return self.buildTreePostIn(0, len(inorder)-1, inorder, 0, len(postorder)-1, postorder, hm) def buildTreePostIn(self, ist, ie, inorder, pst, pe, postorder, hm): if ist > ie or pst > pe: return None root = TreeNode(postorder[pe]) inroot = hm[postorder[pe]] nums_left = inroot - ist root.left = self.buildTreePostIn(ist, inroot - 1, inorder, pst, pst + nums_left - 1,postorder, hm) root.right = self.buildTreePostIn(inroot+1, ie, inorder, pst + nums_left, pe-1,postorder, hm) return root

class Solution { public: int index=0; TreeNode* createTree(vectorpreorder, vectorinorder, int start, int end) { if(start>end) return NULL; TreeNode *node = new TreeNode(preorder[index++]); int pos; for(int i =0;ival) { pos=i; break; } } node->left = createTree(preorder, inorder, start, pos-1); node->right=createTree(preorder, inorder, pos+1,end); return node; } TreeNode* buildTree(vector& preorder, vector& inorder) { return createTree(preorder,inorder,0,inorder.size()-1); } }; how about this, this sems a tad simpler?

class Solution { TreeNode* buildtreepoin(vector&inorder,int ins,int ine,vector&postorder,int pos,int poe,map&hm){ if(pos>poe || ins>ine) return NULL;//size=0 TreeNode* root=new TreeNode(postorder[poe]); int inroot=hm[postorder[poe]]; int numsleft=inroot-ins; root->left=buildtreepoin(inorder,ins,inroot-1,postorder,pos,pos+numsleft-1,hm); root->right=buildtreepoin(inorder,inroot+1,ine,postorder,pos+numsleft,pos-1,hm); return root; } public: TreeNode* buildTree(vector& inorder, vector& postorder) { if(inorder.size()!=postorder.size()) return NULL;//trees can't create maphm; for(int i=0;i

@soumyasharma5378

Жыл бұрын

while traversing in right it should be poe-1 and not pos -1. Dry run and recheck.

completed lecture 35 of free ka tree series.

can we just reverse the post order array and apply the method that we used in preorder??

@krishnarajs8012

2 жыл бұрын

Not possible if you reverse pre order you will not get post order

@your_name96

2 жыл бұрын

I did it after reversing the post order as well as it was easier for me to visualise, but ofcourse the pointer increment decrement will be different. TreeNode * hlp(vector&postorder,int postStart,int postEnd, vector&inorder,int inStart, int inEnd,map&inPos){ // base cases if(postStart > postEnd or inStart > inEnd)return NULL; // first create the root of the tree TreeNode* root = new TreeNode(postorder[postStart]); int inRoot = inPos[root->val]; int numsInRight = inEnd - inRoot; root->left = hlp(postorder,postStart+numsInRight+1,postEnd,inorder,inStart,inRoot-1,inPos); root->right =hlp(postorder,postStart+1,postStart + numsInRight,inorder,inRoot+1,inEnd,inPos); return root; } TreeNode* buildTree(vector& inorder, vector& postorder) { mapinPos; reverse(postorder.begin(),postorder.end()); for(int i=0; i TreeNode *root = hlp(postorder,0,postorder.size()-1,inorder,0,inorder.size()-1,inPos); return root; }

@avicr4727

Жыл бұрын

yes you can do it but keep in after reversing you will get root right left so first half will denote right ans second half will denote left

thanks sir

Understood

I am getting TLE if I don't pass the map by reference can anyone explain why?

@takeUforward

2 жыл бұрын

Creates a copy, so more time. Reference means usung the same!!

@Aryan-fi2qf

2 жыл бұрын

@@takeUforward Thanks for the reply.

able to solve by myself

great content man. I have one query, what if there are duplicate nodes?

@em_ashutosh

2 жыл бұрын

While hashing use whole node.

@maneeshguptanalluru7807

2 жыл бұрын

@@em_ashutosh could you please elaborate your approach?

@aryanbharat9749

2 жыл бұрын

@@maneeshguptanalluru7807 use map then each node is different from one another

@rishabhgupta9846

Жыл бұрын

when searching for root->val search from instart to inend in inorder array

@muthupandideivamsanmugam1774

Жыл бұрын

@@aryanbharat9749 but the input is only a integer type vector 😀

understoodo!!!!

tle on testCase 201(leetcode) for both pre and postorder can anyone help?

@shivamkumar5857

Жыл бұрын

pass every thing by reference

genius

13:00

💚

Done!

Efforts ++

Why solution with unordered_map is taking more runtime than map?

@neelpatel122

2 жыл бұрын

Ideally unordered_map solution is faster. But, leetcode test cases are poor, and when you submit your code again and again you'll see change in runtime.

@amanbhadani8840

2 жыл бұрын

In best case unordered map takes O(1) time but in worst case it takes O(n) time which is more than the average time complexity of ordered map i.e log(n).

In video u have used(giving TLE):- ps+numleft-1 But in github solution it is(CORRECT):- ps+numleft-1-is I am not getting the logic of the github code. Can you please explain the reason?

@vishalgupta957

2 жыл бұрын

did u get the answer??

us

I am getting TLE...Out of 202 cases only 201 got passed :(

@vamsimadugula8524

Жыл бұрын

me too did you find the mistake?

@pragatiagrawal201

Жыл бұрын

@@vamsimadugula8524 Ab to main sab kuch bhool sa gyi hoon haan pr ye na maine check kiya Leetcode pr abhi to dekha ki mera accept ho gya tha. Solution shayad yhi tha pr phir bhi yahan paste kre deti hoon.. mera mood nhin h compare krne ka..shayad maine hi galti ki thi jitna mujhe yad hai. Code jo accept ho gya tha wo ye hai ::: /** * 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& inorder, vector& postorder) { int postStart = 0, postEnd = postorder.size() - 1; int inStart = 0, inEnd = inorder.size() - 1; map mp; for (int i = inStart; i & postorder, int postStart, int postEnd, vector & inorder, int inStart, int inEnd, map & mp) { if (postStart > postEnd || inStart > inEnd) return NULL; TreeNode * root = new TreeNode(postorder[postEnd]); int inRoot = mp[root -> val]; int numsLeft = inRoot - inStart; root -> left = constructTree(postorder, postStart, postStart + numsLeft - 1, inorder, inStart, inRoot - 1, mp); root -> right = constructTree(postorder, postStart + numsLeft, postEnd-1, inorder, inRoot + 1, inEnd, mp); return root; } };

@pranjal-barnwal

Жыл бұрын

@@pragatiagrawal201 The only difference is that Map is passed as reference in 2nd function, so value doesn't get copied again and again. Instead same map is used in multiple calls.

@pragatiagrawal3599

Жыл бұрын

@@pranjal-barnwal Okayyy.. Thanks a lot:)

❤❤

reach++

"us"

why this code is giving TLE in leetcode??

@neelpatel122

2 жыл бұрын

If your logic is correct and still receiving TLE then try passing the vectors and map in the helper function by "reference".

@amitkoushik5504

Жыл бұрын

@@neelpatel122 Thanks buddy, it actually works.

It is giving TLE😭

Similar code but bit simpler way to represent : // for finding index of an element int find(int ele, int in[], int l, int r) { for(int i=l; i r or idxright = build(in, post, pos+1, r , --idx); if(node->right == NULL) idx++; node->left = build(in, post,l, pos -1, --idx ); if(node->left == NULL) idx++; return node; } //Function to return a tree created from postorder and inoreder traversals. Node *buildTree(int in[], int post[], int n) { // Your code here int idx = n-1, l=0, r = n-1; int pos = find(post[idx], in, l, r); Node* node = new Node(post[idx]); node->right = build(in, post, pos+1, r, --idx); if(node->right == NULL) idx++; node->left = build(in, post, l, pos -1, --idx ); return node; }

With the knowledge Of Previous video i done this question on my own here is the code public static TreeNode buildTree2(int[] postorder, int[] inorder) { //Store the inorder in the map Map map=new HashMap(); for(int i=0;i postEnd || inStart > inEnd) { return null; } TreeNode root = new TreeNode(postOrder[postEnd]); //index of the root node int inRoot = map.get(root.val); //nodes in left int numsRight = inEnd - inRoot; root.right = constructBinaryTree2(postOrder, postEnd - numsRight, postEnd - 1, inOrder, inRoot + 1, inEnd, map); root.left = constructBinaryTree2(postOrder, postStart, postEnd - numsRight - 1, inOrder, inStart, inRoot - 1, map); return root; }

Bhai hindi me bol sakte ho kya english samaj ni aati

@amanbhadani8840

2 жыл бұрын

English seekh lene ka re baba,simple.

@amitchaurasia592

2 жыл бұрын

@@amanbhadani8840 bhai tm English medium me padhe hoge hm hindi medium me padhe hai

@amanbhadani8840

2 жыл бұрын

@@amitchaurasia592 Bhai ye bhi 1 essential skill ban chuka hai aajkal and company me phir conversation kaise kroge.Thats why it's better to improve yourself rather than finding excuse.

@amitchaurasia592

2 жыл бұрын

@@amanbhadani8840 aacha bhai phir English seekh leta hu

@amitchaurasia592

2 жыл бұрын

Par philhal ye hindi bole thoda samjhu phir to English ka dekh linga

It's a humble suggestion please refine your explanations it sometimes seems like you are just talking to yourself.

overactor bro

understood

Bhut BAdiya video he sir, hmesha ki trah

Understood

understood

Bhut BAdiya video he sir, hmesha ki trah

Bhut BAdiya video he sir, hmesha ki trah

Bhut BAdiya video he sir, hmesha ki trah

Bhut BAdiya video he sir, hmesha ki trah

Bhut BAdiya video he sir, hmesha ki trah

Bhut BAdiya video he sir, hmesha ki trah

Bhut BAdiya video he sir, hmesha ki trah

Bhut BAdiya video he sir, hmesha ki trah