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

Entire DSA Course: takeuforward.org/strivers-a2z...
Check our Website:
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
#treeSeries #striver #placements

[@takeUforward]

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

[@lavanyam3224]

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

[@tps8470]

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

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

[@sayakbasak587]

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

[@anuragojha3871]

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

[@charlesbabbage6786]

Grateful for these amazing videos!!

[@iamnottech8918]

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

[@de_ansh]

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

[@dpsmartguy]

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

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

[@user-yg2bo9bb7o]

Thanks Striver for such amazing explanation!!!

[@pramodreddy1214]

Thanks man helped me a lot!!

[@dheerajsaraswat227]

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

[@surajbaranwal56.]

Quality Product, keep spreading knowledge , thanks Striver!

[@VineetKumar-fk2rl]

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

[@stith_pragya]

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

[@nuraynasirzade]

thank you VERY MUCH brilliant explanation👏

[@ShariqueAkhtar]

best explanation to this problem

[@ritikshandilya7075]

great explanation

[@poorpanda9033]

Thank you !

[@kambozprav3472]

great explanation !!

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

[@rounakmukherjee9540]

Thats call quality content

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

[@nagavedareddy5891]

Huge respect....❤👏

[@giraffe4375]

Very beautifully explained bhaiya

[@amanbhadani8840]

Nice explanation.

[@mohdnomaankhan2435]

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

[@gyanprakash302]

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

[@suryakiran2970]

Great Explanation

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

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

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

[@sagarghare9829]

bhaiya 1 number explain kiya he :) Thanks

[@alesblaze4745]

thanks mate!

[@sparshsharma6068]

Understood Bhaiya!

[@rishabhkumar8115]

Bhut BAdiya video he sir, hmesha ki trah

[@satyampande684]

understood!!

[@pradeepkundekar4376]

I was able to code by myself 🥳

[@AyushSingh-em2il]

Understood!

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

[@anonymous090]

Thank you Bhaiya

[@UECAshutoshKumar]

Thank you sir

[@rishabhdwivedi5217]

Ahhh nice one ✌

[@harshitjaiswal9439]

understood

[@tle964]

Please try to upload all the videos till Sunday 🙏🙏

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

[@48_subhambanerjee22]

KUDOOOSSSSSS... THIS IS FIREEEE

[@ece155hemanth3]

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

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

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

[@mdshahriarhossain6333]

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

[@ManojKumar-jb4sc]

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

[@shreyasnagabhushan4918]

thanks sir

[@himanshidafouty347]

Understood

[@mriduljain1981]

completed lecture 35 of free ka tree series.

[@jayyy311]

💚

[@bhavya8608]

understoodo!!!!

[@krishnarajs8012]

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

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

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

[@rishabhgupta9846]

able to solve by myself

[@jitinroy2246]

genius

[@satvrii]

❤❤

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

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

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

[@girikgarg8]

Done!

[@rks3522]

13:00

[@pratikdas1780]

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

[@anuj8855]

Exactly 💯

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

[@guptashashwat]

Efforts ++

[@I_Keshav_Prajapati]

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

[@shivamkumar5857]

pass every thing by reference

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

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

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

[@piyushacharya7696]

reach++

[@cenacr007]

us

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

[@suvanshmahajan5902]

"us"

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

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

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

[@radiokepler]

overactor bro

[@adityaprasad6693]

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

[@rishabhkumar8115]

Bhut BAdiya video he sir, hmesha ki trah

[@BLUEPRINTS533]

understood

[@sujan_kumar_mitra]

Understood

[@rishabhkumar8115]

Bhut BAdiya video he sir, hmesha ki trah

[@rishabhkumar8115]

Bhut BAdiya video he sir, hmesha ki trah

[@rishabhkumar8115]

Bhut BAdiya video he sir, hmesha ki trah

[@rishabhkumar8115]

Bhut BAdiya video he sir, hmesha ki trah

[@rishabhkumar8115]

Bhut BAdiya video he sir, hmesha ki trah

[@rishabhkumar8115]

Bhut BAdiya video he sir, hmesha ki trah

[@rishabhkumar8115]

Bhut BAdiya video he sir, hmesha ki trah