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
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.
@@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
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.
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; }
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 ♥️♥️
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!!
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 ...
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.
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; } };
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?
Hey ! Why in morris traversal we cannot talk about space complexity O(N) , as we are taking vector to store all inorder... i didn't understand , can someone explain???
That vector is not considered to be part of algorithmic space. It just stores the answer. Also, we can run the algorithm without it too. Think of it like this. What if instead of pushing element in vector, we just print that element. Then no space would be required.
Please likeeee, shareeee and subscribeeeeeeee :) Also follow me at Insta: Striver_79
Aaaye hi ho, toh series bhi dekh lo ;)
Bilkul.
Just informed to my friends that video is out 😁
Hey striver please add morris postorder traversal
Wonderful explanation bhaiya...
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
Great Job Thanks!
Came here for this. Thank you! ✍👍
In each video I find your comment to take the notes :)
In 3rd case shouldn't it be Remove the thread ..and THEN PRINT NODE AND GO RIGHT??
@@AbhishekYadav-rm4hw Yes, right. You can add it to 'your' notes
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.
Right sir ❤️
They are more interested in "How to get into google" type of videos.
Cute
@@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
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.
To be honest, this was the toughest video of the playlist so far, and obviously not the easiest!
100/100 for the efforts!
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;
}
can you please explain the intuition of connecting leftmost node of right subtree to cur
Just replace left with right and right with left of preorder code. Thanks
@@iamnoob7593 it is wrong
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 ♥️♥️
Bro kidda? 2nd year ki 3rd.
@@karanveersingh5535 😂
@@akashgupta13 😂
Crystal clear explanation! Understanding it from reading articles was really difficult and you made it so simple. Thank you !🙌
I agree. Reading about this algorithm is one thing. Watching the explanation on UA-cam makes it soooo much clearer. 🔊
Yeah, you're right.@@CostaKazistov
The best tutor on UA-cam.
Thank you so much Striver.
This is indeed the best explanation of this series, truly crystal clear.Kudos to your work for the programming community Bhaiya.
I studied it from book but was unable to understand it. But after watching your video understood it completely. Great Explanation!
1 upvote, best explaination brother, and congo for the offers from facebook and google, this news had definitely shut the mouth of haters
✅ 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;
}
Man that''s a great intution
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!!
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 ...
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.
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;
}
};
This is not O(1) space complexity.
@@AlbertoRodriguez-oe6jo do you consider storage space of ans in space complexity?
thanks
Amazingly explained ,the intuition has just fit into my head forever❤️
Almost completed my Binary Trees trees. If I get placed in a good company, the credit goes to you. Love you bro
You did?
@@073.iyasmeenmahilang3 lol
Every time I watch it, things become more clearer. This is the third time in 6 months.
you are best man no one even touch these type of topics
Thank You So Much for this wonderful video............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
That was the best explanation.
Truly epic bhai.
Great Explanation. A bit of a heavy topic, takes time to wrap your head around. Will revisit after a week.
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;
Application of this algo = change links in tree ques. Eg flatten the tree ( next ques of this playlist). 👍👍
Crystal and Clear Explanation for such a difficult topic❤
Superb striver , Man ur excellent
WORDS ARE NOT ENOUGH TO APRRECIATR YOU .....🔥
thank you so much after struggling so much on this topic, I watched your video.
never seen an explaination like this wonderful!
Best explanation of morris traversal..
Best explanation. No one can explain better than this way.
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?
Best explanation.Thanks a lot for making these videos.
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
Literally it was seems Soo horrible now it's seems so easy just because of you thanks a lot ❤️
One of the easiest explanation ever, Thank you strive Bhaiya❤
This was very well explained, thanks a lot.
Very good explanation. Appreciated
this was amazing bro, u made the topic look like a cake walk
such a Awesome Expalanation!!! TYSM!!
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?
We need to remove the thread because the thread pointing to the curr node and this is changing the structure of the tree
Clear explanation from scratch. Thanks
Nothing Better Than this explanation
Actual video starts @2:10
Really amazing explanation. Thanks. Though that AMORTIZED time complexity confuses a bit.
Thank you So much Striver !
Amazing explanation , keep the good work going🙌
Great Explanation till now for Morris Traversal.
Best explanation ever. bhaiya your explaining style is very very good.
preorder : we must push curr->val in preorder before visiting left
inorder: we will visit left then push the curr->val
It took time to understand this, but it's worth it.
what a amazing Explaination man!!
he really made the code easy....
Great content.
Great video, Thanks you a lot...
Complex Concept made Simple, tysm Raj Bhaiya!!!
Great! Very nicely explained!
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 🙂❣️
Every time to rescue. Thank You !
Best explanation of Morris traversals.
All I can say is thank you🙌
best explaination ever ever..... ❤️❤️🙂🙂
couldnt find a code simpler than this on tbt....thanks a ton
Awesome Explanation Striver 🔥
YOU ARE THE BEST! THANK YOU.
fantastic explanation sir it really helped me a lot😀😀
6:00 - 11:00
code walkthru: 14:10
Damn, that is so smart technique.
thanks for the great explanation!
Thank you so much Striver got it thoroughly!
You're pretty good at what you do.Keep going! :)
Interviewer will ask this question like , do the traversal without using recursion or-any extraspace.
10:52 who is the last right guy..
I'm bit confused
Awesome❤❤❤🎉
understood, thank you!!
Very clear explanation! Thanks!
😁😊thanku striver bhai
does morris traversal is also for postorder?
Thank you bhaiya, this video helped me to learn this concept quickly
Can Postorder also be done using Morris Traversal?
Amazing explanation
what if striver we do not remove thread it will affect anymore??
Is Morris Traversal important for interviews?
Yes, if the interviewer says to do some traversal in O(1) auxilliary space
Yes
Love babbar rejected in google interview for not saying Morris traversal
nothing but respect !! Thank you bhaiya for this entire playlist
sir, is it possible to do postorder with morris??
Sucha a beautiful explanation ❤
is is important from placement pov?
Loved and enjoyed a lot 🔥👍👍🔥
Shouldn't the TC be 0(3N) .. N for whole traversal + N for making link + N for breaking link.. Plzz help!
thank you for this explaination
isnt there a morris post order traversal?
Amazing explanation !!! Loved it ...
bawal 🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥
Hare Krishna...! Great Work
The dopamine rush after your code runs on first try >>>
Great great great explaination🎊
great explanation!!!
loving the tree series!!!
Thank You So Much Sir
Why not postorder using Moris Algo?
Hey ! Why in morris traversal we cannot talk about space complexity O(N) , as we are taking vector to store all inorder... i didn't understand , can someone explain???
That vector is not considered to be part of algorithmic space. It just stores the answer. Also, we can run the algorithm without it too. Think of it like this. What if instead of pushing element in vector, we just print that element. Then no space would be required.
@@rhythmbhatia8906 Thankss a lot! Got it now!