L37. Morris Traversal | Preorder | Inorder | 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 Aaaye hi ho, toh series bhi dekh lo ;)

[@user-xi5sm3dz9q]

Bilkul.

[@deepaksarvepalli2344]

Just informed to my friends that video is out 😁

[@PrashantSingh-ej8lz]

Hey striver please add morris postorder traversal

[@priyanshkumar_iitd]

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

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

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

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

[@priyanshkumar_iitd]

Yeah, you're right.@@CostaKazistov

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

[@harshanand4501]

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

[@amanbhadani8840]

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

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

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

[@paryt7696]

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

[@shriyanshjain4444]

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

[@deepakjain4481]

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

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

[@aryanchaurasia1081]

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

[@mohitsingh7793]

Crystal and Clear Explanation for such a difficult topic❤

[@santanu29]

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

[@preetkatiyar969]

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

[@umber3117]

Best explanation.Thanks a lot for making these videos.

[@anshumanprasad5410]

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

[@saisardesai5548]

never seen an explaination like this wonderful!

[@preetisahani5054]

Great! Very nicely explained!

[@iamnoob7593]

Superb striver , Man ur excellent

[@shreyashachoudhary480]

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

[@mayankdham8917]

Best explanation of morris traversal..

[@stith_pragya]

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

[@SohamDutta222]

YOU ARE THE BEST! THANK YOU.

[@kashishsharma6809]

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

[@surabhichoubey2987]

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

[@bharatht5595]

Clear explanation from scratch. Thanks

[@nagasrikuncharapu3736]

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

[@devanshtiwari9163]

Great Explanation till now for Morris Traversal.

[@sumitgupta310]

what a amazing Explaination man!!

[@AmolGautam]

thank you for this explaination

[@anmolswarnkar7707]

This was very well explained, thanks a lot.

[@Flash-qr5oh]

he really made the code easy....

[@jatinsalve364]

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

[@gandhijainamgunvantkumar6783]

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

[@aviadshiber6232]

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

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

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

[@rkalyankumar]

Best explanation of Morris traversals.

[@Ktr_792]

Nothing Better Than this explanation

[@anshumansinghrajawat7242]

Amazing explanation , keep the good work going🙌

[@satyasaineelapala570]

Amazing explanation

[@shreyasnagabhushan4918]

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

[@VinodKumar-by4pt]

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

[@iffatkhan5505]

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

[@harshdeepak3281]

great explanation!!! loving the tree series!!!

[@garvitanagpal]

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

[@MayankLC93]

such a Awesome Expalanation!!! TYSM!!

[@aviralgoel5709]

Actual video starts @2:10

[@AyushSingh-em2il]

Amazing!

[@jaiminsolanki5478]

Complex Concept made Simple, tysm Raj Bhaiya!!!

[@ordinaryhomosapien1181]

Such a wonderful Explanation

[@anubhavpabby6856]

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

[@devils_mercy]

nice explanation

[@TheHorseRaddish]

Very clear explanation! Thanks!

[@morhadi]

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

[@huungryyyy]

😁😊thanku striver bhai

[@sudarshan3901]

Amazing explanation !!! Loved 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

[@user-tk2vg5jt3l]

Thank you Bhaiya

[@dishant930]

Thank you so much Striver got it thoroughly!

[@ananthia5216]

Awesome❤❤❤🎉

[@debjitmaji632]

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

[@ooofrg4492]

After a lots of struggle I got it 😂

[@kdoxfkck]

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

[@Yash-uk8ib]

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

[@shyamalaravind5906]

Wonderful explanation. Please keep it up.

[@SreeCharan-dx7oc]

THANK YOU

[@ygpointoffun9418]

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

[@sathwikabhignan5535]

fantastic explanation sir it really helped me a lot😀😀

[@KartikeyTT]

ty sir

[@kaustubhdwivedi1729]

Every time to rescue. Thank You !

[@rohitraj9515]

does morris traversal is also for postorder?

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

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

[@glebbondarenko67]

Thank you man I got it. It was a good explanation

[@ganeshkamath89]

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

[@AvinashKumar-pb2op]

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

[@saitejajollu2288]

@@AvinashKumar-pb2op 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

[@anmolsingh3482]

Wonderful explanation Sir!

[@vaalarivan_p]

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

[@KBSiddhantKhanna]

Excellent Lecture

[@chirag_ccp]

Awesome Explanation Striver 🔥

[@prakharagarwal8448]

loved the explanation !!

[@rishichowdhury4296]

can we do post order using morris traversal?

[@vidhijain5110]

why we use cur as an object in line no.60

[@Gaurav-vl6ym]

thank you sir

[@deepthi4476]

Can we do postorder also in the same way?

[@vyomgoyal3125]

Can Postorder also be done using Morris Traversal?

[@Abhishek-sn9jm]

one day bunker will share competition with striver

[@satvrii]

Sucha a beautiful explanation ❤

[@tejassrivastava6971]

nicely explained !

[@RishabhKumarRoyVIT]

is is important from placement pov?

[@shashankojha3452]

Great Explanation

[@shineinusa]

All I can say is thank you🙌

[@satwikvarma2804]

Wow, simply amazing

[@studshelper9901]

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

[@namanshah2688]

very well explained thankyou bro...