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.

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

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

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

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

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

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

[@sauravchandra10]

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

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

[@amanbhadani8840]

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

[@kashishsharma6809]

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

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

[@deepakjain4481]

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

[@aviralgoel5709]

Actual video starts @2:10

[@paryt7696]

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

[@saisardesai5548]

never seen an explaination like this wonderful!

[@shreyashachoudhary480]

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

[@zsa208]

Very good explanation. Appreciated

[@aryanchaurasia1081]

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

[@santanu29]

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

[@mayankdham8917]

Best explanation of morris traversal..

[@LazyCoder20]

That was the best explanation. Truly epic bhai.

[@Ktr_792]

Nothing Better Than this explanation

[@Flash-qr5oh]

he really made the code easy....

[@umber3117]

Best explanation.Thanks a lot for making these videos.

[@stith_pragya]

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

[@jatinsalve364]

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

[@iamnoob7593]

Superb striver , Man ur excellent

[@anshumanprasad5410]

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

[@devanshtiwari9163]

Great Explanation till now for Morris Traversal.

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

[@apmotivationakashparmar722]

Thank you So much Striver !

[@subhajyotisaha1020]

Great video, Thanks you a lot...

[@preetkatiyar969]

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

[@anmolswarnkar7707]

This was very well explained, thanks a lot.

[@MayankLC93]

such a Awesome Expalanation!!! TYSM!!

[@kaustubhdwivedi1729]

Every time to rescue. Thank You !

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

[@mohitsingh7793]

Crystal and Clear Explanation for such a difficult topic❤

[@VinodKumar-by4pt]

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

[@giteshkhanna2633]

Great content.

[@preetisahani5054]

Great! Very nicely explained!

[@sumitgupta310]

what a amazing Explaination man!!

[@rkalyankumar]

Best explanation of Morris traversals.

[@satyasaineelapala570]

Amazing explanation

[@shreyasnagabhushan4918]

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

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

[@SohamDutta222]

YOU ARE THE BEST! THANK YOU.

[@iffatkhan5505]

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

[@jaiminsolanki5478]

Complex Concept made Simple, tysm Raj Bhaiya!!!

[@vaalarivan_p]

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

[@gandhijainamgunvantkumar6783]

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

[@akshatlumb409]

4k video really makes a difference

[@AmolGautam]

thank you for this explaination

[@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 🙂❣️

[@morhadi]

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

[@devils_mercy]

nice explanation

[@SatyamKumar-bw4vi]

Hare Krishna...! Great Work

[@aviadshiber6232]

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

[@TheHorseRaddish]

Very clear explanation! Thanks!

[@anshumansinghrajawat7242]

Amazing explanation , keep the good work going🙌

[@dishant930]

Thank you so much Striver got it thoroughly!

[@shineinusa]

All I can say is thank you🙌

[@shubhamrathour9774]

Better understand

[@deepthi4476]

Can we do postorder also in the same way?

[@chirag_ccp]

Awesome Explanation Striver 🔥

[@huungryyyy]

😁😊thanku striver bhai

[@kdoxfkck]

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

[@Abhishek-sn9jm]

one day bunker will share competition with striver

[@ananthia5216]

Awesome❤❤❤🎉

[@AyushSingh-em2il]

Amazing!

[@anubhavpabby6856]

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

[@sathwikabhignan5535]

fantastic explanation sir it really helped me a lot😀😀

[@rajivkumarkale]

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

[@ooofrg4492]

After a lots of struggle I got it 😂

[@karthik-varma-1579]

Watched 2times for Better Understanding.

[@KBSiddhantKhanna]

Excellent Lecture

[@Learnprogramming-q7f]

Thank you Bhaiya

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

[@shyamalaravind5906]

Wonderful explanation. Please keep it up.

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

[@parthkandwal8343]

Understood striver bhaiya

[@satwikvarma2804]

Wow, simply amazing

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

[@SreeCharan-dx7oc]

THANK YOU

[@rhythmbhatia8906]

Thanks

[@satvrii]

Sucha a beautiful explanation ❤

[@sudarshan3901]

Amazing explanation !!! Loved it ...

[@Gaurav-vl6ym]

thank you sir

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

[@UECAshutoshKumar]

Thank you sir