Construct Binary Tree from Inorder and Postorder Traversal - (GOOGLE) : Explanation ➕ Live Coding

[@ciaassasian]

thank you thank you MIK spent half a day on this couldn't understand wasted lot of time watching lot of youtubers but dumb me couldn't get a slightest clue your video just went like water. Man your teaching skills are way too good! Also your checked your LinkedIn Your college junior here xd Thank you for the help :)

[@codestorywithMIK]

You made my day. Thank you ❤️😇 (Let IIEST know that MIK is on KZbin 😁✌️)

[@kalashpatil2486]

Earlier I used to watch striver sir 's video but now I find whether u have made video on that question if yes I go for ur video because the way u explain is just love ❤

[@Vinamrasharma0523]

us moment brother

[@gayatrimamidwar8364]

Previously I tried myself and at that time I understood also then I forgot. Later I was avoiding to go through it again. Now it's crystal clear. Thnx alot bhaiya🙌

[@madhavdhingra_]

Below code also works...Similar to the one like you have explained with inorder and preorder. Just traverse the postorder from right to left and build root first, then right subtree and then left one as for postorder, the sequence is Left -> Right -> Root. class Solution { public: unordered_map mp; TreeNode* solve(vector inorder, vector postorder, int s, int e, int& idx){ if(s > e) return NULL; int rootVal = postorder[idx]; int i = mp[rootVal]; idx--; TreeNode* root = new TreeNode(rootVal); root->right = solve(inorder,postorder,i+1,e,idx); root->left = solve(inorder,postorder,s,i-1,idx); return root; } TreeNode* buildTree(vector& inorder, vector& postorder) { int n = inorder.size(); for(int i=0;i

[@mountINEER]

yo i did same..

[@arpitakar3384]

Arey Bhai jannat hai aapka explaination Hats off efforts

[@sauravchandra10]

Mazedaar explamat Python code: def solve(inorder, postorder, inStart, inEnd, postStart, postEnd): if inStart > inEnd: return None root = Node(postorder[postEnd]) i = 0 while inorder[i] != root.data: i += 1 root.left = solve(inorder, postorder, inStart, i-1, postStart, postStart+leftSize-1) root.right = solve(inorder, postorder, i+1, inEnd, postStart_leftSize, postEnd-1) return root return solve(In, post, 0, n-1, 0, n-1)

[@JJ-tp2dd]

Java implementation: class Solution { private TreeNode solve(int[] inorder, int[] postorder, int inStart, int inEnd, int postStart, int postEnd) { if(inStart > inEnd) { return null; } if(postStart > postEnd) { return null; } TreeNode root = new TreeNode(postorder[postEnd]); // search for this root's position in inorder int i = inStart; for(; i

[@souravjoshi2293]

I understood from your video only. Thanks a lot

[@Sarthak-g3m]

great explaination!!!!!

[@tutuimam3381]

Thanks a lot

[@jayanth1191]

Bhaiya please continue graph concepts 😇

[@codestorywithMIK]

Yesss

[@yuvhrajverma9665]

sir we can also start building tree from right as postorder is L->R->ROOT no when we iterate from end of postorder first we will get the main root after that the secondlastindex is the root of right subtree and so on when our base condition is reaches means we have completed building right subtree and when we return we will start building left subtree int j=-1; TreeNode solve(int s,int e,int in[],int post[]){ if(s>e)return null; System.out.println(j); TreeNode root=new TreeNode(post[j--]); int ind=-1; for(int i=0;i

[@souravjoshi2293]

This should also work. Thanks for sharing

[@yuvhrajverma9665]

@@souravjoshi2293 sir thanks for creating all these videos, sir are u planning to create a playlist of all algorithms and tricks like line sweep , meet in middle algo etc

[@codestorywithMIK]

Hi yuvhraj, that will work too. It’s good that you are trying to explore different ways to solve a problem.

[@codestorywithMIK]

And i think you mentioned wrong person (Asim) above 😁. And sure, i am planning to add those concepts also that you have mentioned. I like your curiosity

[@souravjoshi2293]

@@yuvhrajverma9665 are bhai. Maine nahi ban ye sab 😅. The creator's name is Mazhar , you can find him on linkedIn

[@ramankr0022]

#awesome_mausam

[@prudhvirajmacherla9854]

Sir under which organization are you working present

[@nkvs1248]

Legendary Content !!!

[@codestorywithMIK]

Means a lot to me. Thank you for your kind words 😇🙏

[@gautamchopra9939]

🔥

[@ishitapathak676]

class Solution { public: TreeNode* solve(vector &inorder,vector &postorder,int start,int end,int &idx){ if(start>end) return NULL; int nodeVal = postorder[idx]; int i=start; for(;iright=solve(inorder,postorder,i+1,end,idx); root->left=solve(inorder,postorder,start,i-1,idx); return root; } TreeNode* buildTree(vector& inorder, vector& postorder) { int n=inorder.size(); int idx=n-1; return solve(inorder,postorder,0,n-1,idx); } };

[@vickyjha2283]

I also solved using this solution and it woks same. Then, why we have to solve it using postStart and postEnd ?

[@ishitapathak676]

@@vickyjha2283 both the approach are correct using poststart and postend provides a more explicit way to handle the boundaries of the subarrays representing the left and right subtrees and can be more intuitive for understanding like how recursion divides the problem. In the apporach when using idx-- works well bcz we are decrementing the index of the postorder traversal array as we create nodes. This ensures that we always pick the correct root from the postorder array

[@aizad786iqbal]

i have doubt about the -1, for the postEnd for the left...then right ke start ke liye -1 kyun nahi kara without looking at figure , how can we think ki kab -1 karna hai and kab nahi... baaki sab samjh aa gaya..

[@closer9689]

it's not about adding -1 always.It's just a way of achieving the required index(A value).Bus yeh socho ki current value me kya changes kre ki uski value required value ke barabar ho jaye

[@rdrahuldhiman19]

I solved this with inorder-preorder codewithmk solution, just changed position of some statements in code, below is the JS code. /** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {number[]} inorder * @param {number[]} postorder * @return {TreeNode} */ var buildTree = function(inorder, postorder) { let n = inorder.length; let idx = { val: n-1 } return solve(postorder, inorder, 0, n-1, idx) }; const solve = (postorder, inorder, start, end, idx) => { if(start > end) return null; let rootVal = postorder[idx.val]; let i = start; for(i; i

[@elakstein]

we just need the end index of postorder (postEnd) :: class Solution { private: vector inorder, postorder; unordered_map mp; TreeNode* build(int inStart, int inEnd, int postIndex){ if(inStart > inEnd) return nullptr; int rootPos = mp[postorder[postIndex]]; int rightSize = inEnd-rootPos; TreeNode *root = new TreeNode(inorder[rootPos]); root->left = build(inStart, rootPos-1, postIndex-rightSize-1); root->right = build(rootPos+1, inEnd, postIndex-1); return root; } public: TreeNode* buildTree(vector& inorder, vector& postorder) { this->inorder = inorder; this->postorder = postorder; for(int i=0; i

[@codestorywithMIK]

Thanks a lot for sharing

[@mrboon8856]

We can also do like this class Solution { public: vectorin ,post; int idx; TreeNode* solve(int start,int end) { if(start>end) return NULL; TreeNode* root=new TreeNode(post[idx]); idx--; for(int i=start;ival) { root->right=solve(i+1,end); root->left=solve(start,i-1); break; } return root; } TreeNode* buildTree(vector& inorder, vector& postorder) { in=inorder,post=postorder; idx=post.size()-1; return solve(0,in.size()-1); } };

[@codestorywithMIK]

Thanks for sharing Manish ❤️

[@mrboon8856]

@@codestorywithMIK thanks a lot bro I have learn alot from u. I am lagging in one special type of problems which generally asking about subsequence

[@shubhankarobroye2310]

bhaiya can u plz tell me the time complexity ans space complexity ?

[@yashaggarwal825]

bhaiya plz add todays daily challenge

[@codestorywithMIK]

Coming in a moment. Guaranteed that Trie will become easy now

[@yashaggarwal825]

@@codestorywithMIK thanks!! i have watched many videos but unable to understand the implementation part

[@codestorywithMIK]

Do ensure to focus ok every point i am saying till the end of the video. It will definitely help to make TRIE easy.

[@codestorywithMIK]

Being uploaded now

[@yashaggarwal825]

@@codestorywithMIK yeah for sure

[@santoshmore2953]

Can I implement into javascript using same logic?

[@JJ-tp2dd]

yes @santoshmore2953 we can. let solve = function(inorder, postorder, inStart, inEnd, postStart, postEnd) { if(inStart > inEnd) { return null; } const root = new TreeNode(postorder[postEnd]); let i = inStart; for(; i

[@santoshmore2953]

Hey can u share resources for learning DSA in javascript. From basic to advanced

[@JJ-tp2dd]

@@santoshmore2953 you can start with W3 schools, learn the basics of JavaScript. Once done, practice basic questions like simple loops. Then you can search on youtube for DSA content. This channel has great DSA too, you understand the concept and then you can implement JS solution on your own. Keep referring MDN docs as well for JS. Keep practicing.

[@santoshmore2953]

@@JJ-tp2dd k tq

[@elakstein]

Nice explanation 👍 Are you in college or working?

[@molyoxide8358]

He's currently working

[@elakstein]

@@molyoxide8358 okay moly. what about you ?

[@molyoxide8358]

@@elakstein Struggling

[@AYJ959]

@@molyoxide8358 😂

[@molyoxide8358]

Bro mene same code lika par runtime error aa gya code: class Solution { public: TreeNode* create(vector& inorder, vector& postorder, int inStart, int inEnd, int postStart, int postEnd) { if(inStart > inEnd){ return NULL; } TreeNode* root = new TreeNode(postorder[postEnd]); int i = inStart; for(; ival) break; } int leftSize = i - inStart; int rightSize = inEnd - i; root->left = create(inorder, postorder, inStart, i-1, postStart, postStart+leftSize-1); root->right = create(inorder, postorder, i+1, inEnd, postStart-rightSize, postEnd-1); return root; } TreeNode* buildTree(vector& inorder, vector& postorder) { int n = inorder.size(); int inStart = 0; int inEnd = n-1; int postStart = 0; int postEnd = n-1; return create(inorder, postorder, inStart, inEnd, postStart, postEnd); } };

[@codestorywithMIK]

This is same code. Strange. It should work. Is it resolved ? Or should i check it from my side ?

[@molyoxide8358]

@@codestorywithMIK Yeah I found the mistake after spending 45 mins. Instead of writing postEnd-rightSize, I wrote postStart-rightSize

[@codestorywithMIK]

Great to hear you figured it out

[@molyoxide8358]

@@codestorywithMIK BTW thanks for making videos as well as solving doubts.