L35. Construct the Binary Tree from Postorder and Inorder Traversal | C++ | Java

[@takeUforward]

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

[@lavanya_m01]

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

[@kshittizbhardwaj417]

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

[@sarangtamrakar8723]

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

[@tps8470]

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

[@sayakbasak587]

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

[@CharitraAgarwal]

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.

[@Mel-up7un]

striver no one, I repeat NO ONE has the level of your explanation and understanding.Hat's off man!

[@NMCSMROHANHEGDE]

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

[@rahulkumarbarik7584]

thanks for help bro, worked for me

[@knowhere6073]

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

[@rahulsrivastava1040]

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

[@abhishekdhok5245]

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

[@adityamaurya6646]

Was able to solve this problem on my own bcz I watched the previous explaination!! Taught beautifully

[@anuragojha3871]

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

[@AnirudhSingh-y8q]

You are deserve for like because no any youtubers do labour like you ❤

[@iamnottech8918]

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

[@shreyxnsh.14]

started travelling from the back and pushed right first then the left: class Solution { public: unordered_map inMap; TreeNode* buildTreeHelper(vector &postorder, int &postIndex, int inStart, int inEnd){ if(inStart > inEnd) return NULL; int root_val = postorder[postIndex--]; TreeNode* node = new TreeNode(root_val); int index = inMap[root_val]; node->right = buildTreeHelper(postorder, postIndex, index+1, inEnd); node->left = buildTreeHelper(postorder, postIndex, inStart, index-1); return node; } TreeNode* buildTree(vector& inorder, vector& postorder) { for (int i = 0; i < inorder.size(); ++i) { inMap[inorder[i]] = i; } int postIndex = postorder.size()-1; return buildTreeHelper(postorder, postIndex, 0, inorder.size() - 1); } };

[@rounakmukherjee9540]

Thats call quality content

[@dheerajsaraswat227]

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

[@rydmerlin]

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.

[@omtayade9758]

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]

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]

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

[@dpsmartguy]

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

[@MousamiDeshmukh-g8k]

Thanks Striver for such amazing explanation!!!

[@aanchalmittal9897]

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?

[@VineetKumar-fk2rl]

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

[@stith_pragya]

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

[@242deepak]

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

[@nuraynasirzade]

thank you VERY MUCH brilliant explanation👏

[@ShariqueAkhtar]

best explanation to this problem

[@de_ansh]

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

[@apmotivationakashparmar722]

Thank you Striver !

[@mohdnomaankhan2435]

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

[@afaqueahmed3882]

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

[@surajbaranwal56.]

Quality Product, keep spreading knowledge , thanks Striver!

[@sagarghare9829]

bhaiya 1 number explain kiya he :) Thanks

[@ritikshandilya7075]

great explanation

[@developer00007]

I was able to code by myself 🥳

[@mudita3366]

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

[@vishalsagar1437]

did you get the answer to this. if yes please share Thanks

[@PiyushKumar-xe1ng]

@@vishalsagar1437 try to pass the inmap using reference

[@giraffe4375]

Very beautifully explained bhaiya

[@gyanprakash302]

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

[@sethunagakarthikm4022]

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

[@charlesbabbage6786]

Grateful for these amazing videos!!

[@pramodreddy1214]

Thanks man helped me a lot!!

[@nagavedareddy5891]

Huge respect....❤👏

[@rishikchakravarty7986]

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?

[@sparshsharma6068]

Understood Bhaiya!

[@tle964]

Please try to upload all the videos till Sunday 🙏🙏

[@pratyush7987]

Thanks a ton!

[@amanbhadani8840]

Nice explanation.

[@pratikdas1780]

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

[@anuj8855]

Exactly 💯

[@theultimatespo...4205]

Agree bro😂

[@suryakiran2970]

Great Explanation

[@ece155hemanth3]

How will be the BFS approach for this problem will it be possible

[@UECAshutoshKumar]

Thank you sir

[@kambozprav3472]

great explanation !!

[@ShubhamKumar-et7gx]

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.

[@poorpanda9033]

Thank you !

[@mriduljain1981]

completed lecture 35 of free ka tree series.

[@rishabhkumar8115]

Bhut BAdiya video he sir, hmesha ki trah

[@amriteshkumar5557]

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 ?

[@ManojKumar-jb4sc]

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

[@48_subhambanerjee22]

KUDOOOSSSSSS... THIS IS FIREEEE

[@mdshahriarhossain6333]

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

[@prateekjoshi6425]

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

[@takeUforward]

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

[@prateekjoshi6425]

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

[@kwanikar7]

@@prateekjoshi6425 try passing the map by reference

[@prakharmangal1152]

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

[@supratimbhattacharjee5324]

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

[@anonymous090]

Thank you Bhaiya

[@rishabhdwivedi5217]

Ahhh nice one ✌

[@gksindu3363]

class Solution: def __init__(self): self.mydict={} def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]: for i,j in enumerate(inorder): self.mydict[j]=i return self.construct(inorder,postorder) def construct(self,inorder,postorder): if not inorder or not postorder: return None t=self.createnode(postorder[-1]) #ind=inorder.index(postorder[-1]) curr=postorder[-1] ind=self.mydict[curr] length=len(inorder[0:ind]) t.left=self.construct(inorder[:ind],postorder[:length]) t.right=self.construct(inorder[ind+1:],postorder[length:-1]) return t def createnode(self,data): t=TreeNode(data) return t whats wrong with my code why its giving maximum recursion depth when im trying to access the hashmap

[@DeadPoolx1712]

UNDERSTOOD;

[@alesblaze4745]

thanks mate!

[@HarivanshKripaVlogs]

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]

did u get the answer??

[@AyushSingh-em2il]

Understood!

[@rishabhgupta9846]

able to solve by myself

[@per.seus._]

understood

[@lavudyabharath8783]

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

[@krishnarajs8012]

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

[@your_name96]

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 < inorder.size(); i++)inPos[inorder[i]] = 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

[@krishnarajs8012]

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

[@Aryan-fi2qf]

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

[@takeUforward]

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

[@Aryan-fi2qf]

@@takeUforward Thanks for the reply.

[@rks3522]

13:00

[@himanshidafouty347]

Understood

[@heyprashant]

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

[@em_ashutosh]

While hashing use whole node.

[@maneeshguptanalluru7807]

@@em_ashutosh could you please elaborate your approach?

[@rishabhgupta9846]

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

[@muthupandideivamsanmugam1774]

@Aryan Bharat but the input is only a integer type vector 😀

[@girikgarg8]

Done!

[@JohnWick-kh7ow]

Why solution with unordered_map is taking more runtime than map?

[@neelpatel122]

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]

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

[@shreyasnagabhushan4918]

thanks sir

[@I_Keshav_Prajapati]

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

[@shivamkumar5857]

pass every thing by reference

[@satyampande684]

understood!!

[@satvrii]

❤❤

[@jitinroy2246]

genius

[@bhavya8608]

understoodo!!!!

[@guptashashwat]

Efforts ++

[@sujan_kumar_mitra]

Understood

[@pragatiagrawal201]

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 < int, int > mp; for (int i = inStart; i & postorder, int postStart, int postEnd, vector < int > & inorder, int inStart, int inEnd, map < int, int > & 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:)

[@vivekshrivastav3674]

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

[@ajayypalsingh]

💚

[@piyushacharya7696]

reach++

[@suvanshmahajan5902]

"us"

[@codewithom11]

It is giving TLE😭

[@_PRANAYMATE]

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

[@nileshsinha7869]

why this code is giving TLE in leetcode??

[@neelpatel122]

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.

[@cenacr007]

us

[@adityaprasad6693]

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

[@amitchaurasia592]

Bhai hindi me bol sakte ho kya english samaj ni aati

[@amanbhadani8840]

English seekh lene ka re baba,simple.

[@amitchaurasia592]

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

[@amanbhadani8840]

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

@@amanbhadani8840 aacha bhai phir English seekh leta hu

[@amitchaurasia592]

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

[@rishabhkumar8115]

Bhut BAdiya video he sir, hmesha ki trah

[@harshitjaiswal9439]

understood