L37. Morris Traversal | Preorder | Inorder | C++ | Java

[@takeUforward]

Please likeeee, shareeee and subscribeeeeeeee :) Also follow me at Insta: Striver_79 Aaaye hi ho, toh series bhi dekh lo ;)

[@2020-t1z]

Bilkul.

[@deepaksarvepalli2344]

Just informed to my friends that video is out 😁

[@PrashantSingh-ej8lz]

Hey striver please add morris postorder traversal

[@priyanshkumar17]

Wonderful explanation bhaiya...

[@uRamPlus]

Self notes: In-order Morris Traversal: 🌳 1st case: if left is null, print current node and go right 🌳 2nd case: before going left, make right most node on left subtree connected to current node, then go left 🌳 3rd case: if thread is already pointed to current node, then remove the thread

[@TheElevatedGuy]

Great Job Thanks!

[@CostaKazistov]

Came here for this. Thank you! ✍👍

[@gandhijainamgunvantkumar6783]

In each video I find your comment to take the notes :)

[@AbhishekYadav-rm4hw]

In 3rd case shouldn't it be Remove the thread ..and THEN PRINT NODE AND GO RIGHT??

[@parthsalat]

@@AbhishekYadav-rm4hw Yes, right. You can add it to 'your' notes

[@deepanshukhanna1780]

Looking at the views of this video , I think this is the reason people don't make quality stuff, today's generation is more interested in watching those hypothetical motivational videos but not interested in watching what it takes to achieve your goals. Hat's off to you. Keep making such videos. Thanks a lot.

[@KunalSinghStatus]

Right sir ❤️

[@vivekjaiswar6825]

They are more interested in "How to get into google" type of videos.

[@01_abhijeet49]

Cute

[@AdityaKumar-be7hx]

@@vivekjaiswar6825 True. I will also add that these are the contents of videos that actually answers the question "How to get into G?" :) By becoming truly great in solving problems

[@thomasshelby6780]

bro it doesn't take a lot to mind one's own business. Stop taking a jibe at others. Those guys might be good at thousand things that you aren't. Better if you quit perpetuating a rat race in tech that is there already.

[@sparshsharma6068]

By far THE BEST explanation of Morris traversal on youtube!!! Maza aagya bhaiya🔥🔥 and Happy birthday bhaiya. Thank you for being the teacher and a senior we all wanted in our lives🎉🎉 Here's the postorder morris traversal(similar to preorder), the only changes are instead of finding the rightmost node in the left subtree, we find the leftmost node in the right subtree. Also, we need to keep adding the node values in the head so as to maintain the LRN order of postorder. public List postorderTraversal(TreeNode root) { List arr = new LinkedList(); TreeNode curr = root; while(curr != null){ if(curr.right == null){ arr.add(0,curr.val); curr = curr.left; } else{ TreeNode temp = curr.right; while(temp.left != null && temp.left != curr) temp = temp.left; if(temp.left == null){ temp.left = curr; arr.add(0,curr.val); curr = curr.right; } else{ temp.left = null; curr = curr.left; } } } return arr; }

[@kannank4269]

can you please explain the intuition of connecting leftmost node of right subtree to cur

[@iamnoob7593]

Just replace left with right and right with left of preorder code. Thanks

[@abhisheknag1929]

@@iamnoob7593 it is wrong

[@anmolkohli6299]

Crystal clear explanation! Understanding it from reading articles was really difficult and you made it so simple. Thank you !🙌

[@CostaKazistov]

I agree. Reading about this algorithm is one thing. Watching the explanation on KZbin makes it soooo much clearer. 🔊

[@priyanshkumar17]

Yeah, you're right.@@CostaKazistov

[@slowedReverbJunction]

Seriously bhaiya You are man of your words You said that this will be the best explanation of Morris Traversal And you proved it Hats off to to bhaiya 💪👏👏 Thank u sooo much for this awesome content ♥️♥️

[@karanveersingh5535]

Bro kidda? 2nd year ki 3rd.

[@akashgupta13]

@@karanveersingh5535 😂

[@parthsalat]

@@akashgupta13 😂

[@shreyanshpatil8303]

DRY RUN OF THE INPUT Start at the Root: curr = 1 Current ans = [] First Iteration: curr = 1 curr->left = 2, so we find the inorder predecessor (prev) in 2's subtree. Traverse prev to the rightmost node of 2's subtree: prev = 2 → prev->right = 5 prev = 5 → prev->right = 6 prev = 6 Set 6->right = 1 (temporary link). Move curr = 2. Current ans = [] Second Iteration: curr = 2 curr->left = 4, find the inorder predecessor (prev) in 4's subtree: prev = 4 (rightmost node) Set 4->right = 2. Move curr = 4. Current ans = [] Third Iteration: curr = 4 curr->left = NULL, so append 4 to ans. Move curr = 2 (via 4->right). Current ans = [4] Fourth Iteration: curr = 2 (from temporary link) 4->right is already set to 2, indicating the left subtree is processed. Remove temporary link 4->right = NULL. Append 2 to ans. Move curr = 5 (right child of 2). Current ans = [4, 2] Fifth Iteration: curr = 5 curr->left = NULL, so append 5 to ans. Move curr = 6 (right child of 5). Current ans = [4, 2, 5] Sixth Iteration: curr = 6 curr->left = NULL, so append 6 to ans. Move curr = 1 (via 6->right). Current ans = [4, 2, 5, 6] Seventh Iteration: curr = 1 (from temporary link) 6->right is already set to 1, indicating the left subtree is processed. Remove temporary link 6->right = NULL. Append 1 to ans. Move curr = 3 (right child of 1). Current ans = [4, 2, 5, 6, 1] Eighth Iteration: curr = 3 curr->left = NULL, so append 3 to ans. Move curr = NULL. Current ans = [4, 2, 5, 6, 1, 3] End: curr = NULL, and there are no more nodes to process.

[@shwetanksingh5208]

For post order Morris Traversal-> We will modify the preorder morris traversal from root->left->right to root->right->left. For this we need to do one more change. While in normal preorder and inorder, we were creating thread from right most node of left subtree to present node, here we will create thread from left most node of right subtree to present node as here we have to cover right subtree before left subtree class Solution { public: vector postorderTraversal(TreeNode* root) { vector ans; while(root) { TreeNode *curr = root;//We will create thread from left most node of right subtree to present node and will //travell to that node using curr if(curr->right)//if root has right child //We can't push directly this root node val to ans as we are not sure whether we are here //thorough thread link after covering right subtree or we are here for the first time { curr = curr->right; while(curr->left && curr->left != root)//go to left most node of right subtree curr=curr->left; if(curr->left != root)//not threaded yet { ans.push_back(root->val);//it means root was visited for first time and this is modified preorder hence //push this node's val to ans curr->left = root;//create the thread root = root->right;//go to right to cover right subtree as modified preorder is root->right->left } else//was threaded { curr->left = NULL;//break the thread root = root->left;//right subtree has been covered hence now cover the left one //no need to push this node value as we are here for the second time using thread //link } } else//root hasn't right child { ans.push_back(root->val);//modified preorder is root->right->left hence push this value before going to left root = root->left; } } reverse(ans.begin(),ans.end());//reversing root->right->left to left->right->root to make it post order return ans; } };

[@AlbertoRodriguez-oe6jo]

This is not O(1) space complexity.

[@shwetanksingh5208]

@@AlbertoRodriguez-oe6jo do you consider storage space of ans in space complexity?

[@Rajat_maurya]

thanks

[@harshanand4501]

I studied it from book but was unable to understand it. But after watching your video understood it completely. Great Explanation!

[@abhijeetmishra3804]

In starting i was like this video need improvement but after a certain time it was STRIVER show and this was so easy to understand. Thank You Striver ...

[@amanbhadani8840]

This is indeed the best explanation of this series, truly crystal clear.Kudos to your work for the programming community Bhaiya.

[@pankajvishwakarma3124]

✅ Postorder || Morris Traversal vector postorderTraversal(TreeNode* root) { vector postorder; TreeNode* cur= root; while(cur){ if(!cur->right){ postorder.push_back(cur->val); cur=cur->left; }else{ TreeNode* prev=cur->right; while(prev->left && prev->left!=cur){ prev=prev->left; } if(prev->left==NULL){ prev->left=cur; postorder.push_back(cur->val); cur=cur->right; }else{ prev->left=NULL; cur=cur->left; } } } reverse(postorder.begin(),postorder.end()); return postorder; }

[@SibiRanganathL]

Man that''s a great intution

[@JamesHalpert8555]

Beautifully explained!! I watched another lecture but was struggling to come up with morris version for other traversals,now it's crystal clear thank you!!

[@sauravchandra10]

Every time I watch it, things become more clearer. This is the third time in 6 months.

[@sahilverma1991]

Morris Traversal for Post Order Traversal // postorder -> left, right, node // reverse of postorder is -> node right left // we modify Code of Morris Traversal for preorder ( which is node, left , right) vector ans; while(root){ if(root->right == nullptr){ ans.push_back(root->val); root = root->left; }else{ auto temp = root->right; while(temp->left && temp->left != root){ temp = temp->left; } if(temp->left == nullptr){ temp->left = root; ans.push_back(root->val); root = root->right; }else{ temp->left = nullptr; root = root->left; } } } reverse(ans.begin(), ans.end()); return ans;

[@shriyanshjain4444]

To be honest, this was the toughest video of the playlist so far, and obviously not the easiest! 100/100 for the efforts!

[@studshelper9901]

preorder : we must push curr->val in preorder before visiting left inorder: we will visit left then push the curr->val

[@paryt7696]

1 upvote, best explaination brother, and congo for the offers from facebook and google, this news had definitely shut the mouth of haters

[@aryanchaurasia1081]

Amazingly explained ,the intuition has just fit into my head forever❤️

[@deepakjain4481]

you are best man no one even touch these type of topics

[@saisardesai5548]

never seen an explaination like this wonderful!

[@kashishsharma6809]

Application of this algo = change links in tree ques. Eg flatten the tree ( next ques of this playlist). 👍👍

[@santanu29]

Great Explanation. A bit of a heavy topic, takes time to wrap your head around. Will revisit after a week.

[@shreyashachoudhary480]

Really amazing explanation. Thanks. Though that AMORTIZED time complexity confuses a bit.

[@jatinsalve364]

Interviewer will ask this question like , do the traversal without using recursion or-any extraspace.

[@zsa208]

Very good explanation. Appreciated

[@stith_pragya]

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

[@umber3117]

Best explanation.Thanks a lot for making these videos.

[@adityan5302]

Almost completed my Binary Trees trees. If I get placed in a good company, the credit goes to you. Love you bro

[@073.iyasmeenmahilang3]

You did?

[@natanshisharma8828]

@@073.iyasmeenmahilang3 lol

[@anshumanprasad5410]

thank you so much after struggling so much on this topic, I watched your video.

[@mayankdham8917]

Best explanation of morris traversal..

[@LazyCoder20]

That was the best explanation. Truly epic bhai.

[@Ktr_792]

Nothing Better Than this explanation

[@preetkatiyar969]

Best explanation. No one can explain better than this way.

[@amanali9501]

why there is a need to remove a thread ? if it exists on that element it mean its left side is visited , so one can go to right directly

[@bharatht5595]

Clear explanation from scratch. Thanks

[@iamnoob7593]

Superb striver , Man ur excellent

[@aviralgoel5709]

Actual video starts @2:10

[@anmolswarnkar7707]

This was very well explained, thanks a lot.

[@mohitsingh7793]

Crystal and Clear Explanation for such a difficult topic❤

[@devanshtiwari9163]

Great Explanation till now for Morris Traversal.

[@apmotivationakashparmar722]

Thank you So much Striver !

[@Flash-qr5oh]

he really made the code easy....

[@subhajyotisaha1020]

Great video, Thanks you a lot...

[@surabhichoubey2987]

Literally it was seems Soo horrible now it's seems so easy just because of you thanks a lot ❤️

[@nagasrikuncharapu3736]

It took time to understand this, but it's worth it.

[@giteshkhanna2633]

Great content.

[@VinodKumar-by4pt]

One of the easiest explanation ever, Thank you strive Bhaiya❤

[@akshatlumb409]

4k video really makes a difference

[@morhadi]

The dopamine rush after your code runs on first try >>>

[@sumitgupta310]

what a amazing Explaination man!!

[@MayankLC93]

such a Awesome Expalanation!!! TYSM!!

[@rkalyankumar]

Best explanation of Morris traversals.

[@shreyasnagabhushan4918]

this was amazing bro, u made the topic look like a cake walk

[@preetisahani5054]

Great! Very nicely explained!

[@iffatkhan5505]

couldnt find a code simpler than this on tbt....thanks a ton

[@gandhijainamgunvantkumar6783]

Best explanation ever. bhaiya your explaining style is very very good.

[@ooofrg4492]

After a lots of struggle I got it 😂

[@Aryan-fi2qf]

I am getting Runtime error when trying run code without removing thread, We are moving right of curr node as we reach the rightmost of left subtree of curr node, so why do we need to remove the thread?

[@divyansh2212]

We need to remove the thread because the thread pointing to the curr node and this is changing the structure of the tree

[@Abhishek-sn9jm]

one day bunker will share competition with striver

[@satyasaineelapala570]

Amazing explanation

[@pranjalck]

Thanks striver for making me feel like i could also think like this and approach like this... Thank u for Making me believe in myself 🙂❣️

[@SohamDutta222]

YOU ARE THE BEST! THANK YOU.

[@aviadshiber6232]

Damn, that is so smart technique. thanks for the great explanation!

[@kaustubhdwivedi1729]

Every time to rescue. Thank You !

[@jaiminsolanki5478]

Complex Concept made Simple, tysm Raj Bhaiya!!!

[@dishant930]

Thank you so much Striver got it thoroughly!

[@LuckyKumar-mt9km]

going left then going till the last right guy , that is called predecessor of current . It would have been more clearer if you had used that term in the explanation.

[@sanyummanhas1994]

at 4:26 what does he say a single kind of a Quadret??....i didnt quite get it, Can someone tell me what it is?

[@ganeshkamath89]

Thanks Striver. I didn't understand why space complexity became O(1)

[@AkGautam_1904]

Because we are just playing with pointers and not storing anything.

[@saitejajollu2288]

@@AkGautam_1904 it is clearly visible that he is adding the curr->val to the vector and returning the vector how can it be O(1).

[@sumitkanth5349]

@@saitejajollu2288 vector space will we not counted because it was given in ques that we have to return a vector of inorder traversal

[@anshumansinghrajawat7242]

Amazing explanation , keep the good work going🙌

[@huungryyyy]

😁😊thanku striver bhai

[@karthik-varma-1579]

Watched 2times for Better Understanding.

[@sharath5796]

Python Code: preorder=[] cur=root while cur: if cur.left == None: preorder.append(cur.val) cur=cur.right else: prev=cur.left while prev.right and prev.right!=cur: prev=prev.right if prev.right==None: prev.right=cur preorder.append(cur.val) cur=cur.left else: prev.right=None cur=cur.right return preorder

[@vaalarivan_p]

6:00 - 11:00 code walkthru: 14:10

[@AmolGautam]

thank you for this explaination

[@TheHorseRaddish]

Very clear explanation! Thanks!

[@chirag_ccp]

Awesome Explanation Striver 🔥

[@apmotivationakashparmar722]

Can you please provide the Video Solution of remaining Questions in your A-2 Z Sheet ?

[@shineinusa]

All I can say is thank you🙌

[@kdoxfkck]

best explaination ever ever..... ❤️❤️🙂🙂

[@anubhavpabby6856]

Thank you bhaiya, this video helped me to learn this concept quickly

[@devils_mercy]

nice explanation

[@SatyamKumar-bw4vi]

Hare Krishna...! Great Work

[@siddwivedi9643]

nothing but respect !! Thank you bhaiya for this entire playlist

[@rajivkumarkale]

link should have been the correct term intead of thread as thread means something else. BTW good explaination.

[@muskankalra2516]

Is Morris Traversal important for interviews?

[@priyanshkumar17]

Yes, if the interviewer says to do some traversal in O(1) auxilliary space

[@Anonymous____________A721]

Yes Love babbar rejected in google interview for not saying Morris traversal

[@sathwikabhignan5535]

fantastic explanation sir it really helped me a lot😀😀

[@Yash-uk8ib]

sir, is it possible to do postorder with morris??

[@deepthi4476]

Can we do postorder also in the same way?

[@shyamalaravind5906]

Wonderful explanation. Please keep it up.

[@ananthia5216]

Awesome❤❤❤🎉

[@garvitanagpal]

You're pretty good at what you do.Keep going! :)

[@KhushiVerma-y6t]

You made tree easy to me 🙂

[@ygpointoffun9418]

what if striver we do not remove thread it will affect anymore??

[@debjitmaji632]

Shouldn't the TC be 0(3N) .. N for whole traversal + N for making link + N for breaking link.. Plzz help!

[@satyarajrana5702]

I don't understand how this is better than simple recursive preorder traversal? Because this approach also had O(N) space complexity right?

[@SahilMathur-z1w]

o(1) we are using only a temppointer

[@AyushSingh-em2il]

Amazing!

[@mriduljain1981]

completed lecture 37 of free ka tree series.

[@sudarshan3901]

Amazing explanation !!! Loved it ...