I have skipped Morris Traversal for the past 7 years because I never understood it. Turns out, I only had to watch this 10 minute clip. Thanks a ton man.
Wow the intro is so good!! now I understand why thread(link) is needed! bc we have to come back root, without stack or recursion! wow Thanks my teacher!!!
Hi Tushar. I want to thank you for this video. I looked at almost all sources that explain morris traversal but yours actually made everything clear in my mind. Keep making more videos like this. Thanks again.
It’s a good explanation for those looking in to the problem already and stuck with solving it. For those looking in to the problem first time, it would help if the pace of explanation is bit slower.
There's a LOT of bad articles poorly explaining this, and I gave up after checking a few. This cleared it up pretty quickly. I do wish in his first pass he hadnt abstracted findPredecessor() into some invisible function.
Excellent explanation of Morris Algorithm !! keep up the good wrk Tushar !! I keenly follow your videos and they are immensely helpful in understanding concepts of Compute rScience.
there is a problem at 6:45 , after visiting -1 , we got to 2 , then we begin finding predecessor of 2 , Alas , finding predecessor of 2 means going right most in left sub-tree of 2 , here left subtree is -1 , then lets find predecessor ,-1 -> right = 2 , then 2-> right = 5 , 5-> right = 6 , 6-> right = 8 , 8 ->right = 10 , we are moving in totally different direction ....now . Actually this must stop when predecessor is found , but for predecessor , we keep moving right ? Edit: Now I saw the final code , while finding predecessor , you solved the problem by doing , predecessor-> right = current , then break .
Tushar, Great effort on the explanation. But, it seems your algorithm on the board was incomplete (like when the predecessor->right hits the current item itself, then it should stop). Although, you do talk about it while you showcased the code. Also, When you said current becomes current-> right @7:27 , you should actually be pointing at the last else section of your algorithm.
I think the worst case time complexity will be O(n^2). Correct me if I am wrong. Coz we will have to find inorder predecessor for all nodes. And in case of skwed tree, it will take O(n^2) time.
well explained Tushar.. Just one comment for the viewers this Morris approach can be for Pre order traversal also ..and with just 1 line change in the existing code..( let it be a exercise for the viewers)
For Morris Postorder feel free to take a look at www.thealgorists.com/Algo/Tree/MorrisPostorder . Morris Postorder algorithm and code are beautifully explained there.
Thanks for your hard work for making such nice videos! But it would be great if the video explains algorithm derived from concept behind it. What I understand, concpet is the first thing then algo comes. You explan such a way where algo comes first then explain the concept based on the algo! Thank you!
predecessor.right will always be null right? Because if a predecessor of a current node has a right child, then that right child is the predecessor of the current node, no?
Good luck to everyone working hard to be at good tech companies. Thank you for the explanation.
so nice 😊
came here when I didn't get the geeksforgeeks explanation. you have explained it lucidly.
I came like that as well. Lol!
same her bro..
Me too
Me too :-)
Me too:}
I have skipped Morris Traversal for the past 7 years because I never understood it. Turns out, I only had to watch this 10 minute clip. Thanks a ton man.
Man I spent like 2 hours trying to understand the code, but visually seeing it step by step made it finally make sense, thanks!
OK man
Thank you! This was the best explanation I found. Instead of going straight into algorithm, Tushar explained the thought behind it. Great job.
Almost I gave my 2 hours to understand this algorithms on others channel but when I watched this video I got it. Great explanation.
Out of all Morris algorithm explanations out there, yours is so much better. Thank you!
Thank you Tushar! Your video is always a guarantee of crystal clarity. Kudos!
You never fail to impress. Your explanations are always crystal clear and easy to understand. Thanks for sharing your knowledge!!
Thank you! This is the most thorough video explanation on Morris Traversal that I have been able to find.
Best explanation ever. Better than pepcoding, better than Striver.
Same thoughts
Wow the intro is so good!! now I understand why thread(link) is needed! bc we have to come back root, without stack or recursion! wow Thanks my teacher!!!
his diagram is clean and clear enough to demonstrate the concept
Hi Tushar. I want to thank you for this video. I looked at almost all sources that explain morris traversal but yours actually made everything clear in my mind. Keep making more videos like this. Thanks again.
It’s a good explanation for those looking in to the problem already and stuck with solving it. For those looking in to the problem first time, it would help if the pace of explanation is bit slower.
The best explanation I found on youtube so far
Thanks tushar For explaining in simple manner with algorithm and code.
There's a LOT of bad articles poorly explaining this, and I gave up after checking a few. This cleared it up pretty quickly. I do wish in his first pass he hadnt abstracted findPredecessor() into some invisible function.
I am very thankful for your clear explanation and pronunciation!
Best person to explain complex topics. I wonder why his channel is not very famous?
Excellent explanation of Morris Algorithm !! keep up the good wrk Tushar !! I keenly follow your videos and they are immensely helpful in understanding concepts of Compute rScience.
Best explanation of Morris traversal on the internet
your speaking is way better than others
Beautifully explained, thank you. Subbed.
there is a problem at 6:45 , after visiting -1 , we got to 2 , then we begin finding predecessor of 2 ,
Alas , finding predecessor of 2 means going right most in left sub-tree of 2 ,
here left subtree is -1 , then lets find predecessor ,-1 -> right = 2 , then 2-> right = 5 , 5-> right = 6 , 6-> right = 8 , 8 ->right = 10 , we are moving in totally different direction ....now .
Actually this must stop when predecessor is found , but for predecessor , we keep moving right ?
Edit: Now I saw the final code , while finding predecessor , you solved the problem by doing , predecessor-> right = current , then break .
thank you for the video!! but at 7:27 current = current.right, but you were pointing to the wrong place on the white board.
Man, you are always so helpful explaining those fancy algorithms.
Loved your explanation
awesome explanation Much much better than Geeks for geeks
Thanks, best video on this algorithm!
Tushar, Great effort on the explanation. But, it seems your algorithm on the board was incomplete (like when the predecessor->right hits the current item itself, then it should stop). Although, you do talk about it while you showcased the code. Also, When you said current becomes current-> right @7:27 , you should actually be pointing at the last else section of your algorithm.
exactly, i was also confused by that pointing...
i really appreciate the hard work to teach us thank you
The best video about morris! Love your video!
Very nice explanation 🙌🙌
Nice explanation sir...
Thanks for your explanation! I was confused about Morris Traversal, but you video make me clear now.
Thank you for all your videos :)
Thank you very much for the clear explanation.
I think the worst case time complexity will be O(n^2). Correct me if I am wrong. Coz we will have to find inorder predecessor for all nodes. And in case of skwed tree, it will take O(n^2) time.
The TC will still be 2N which is O(N) as the nodes visited at max twice.
A+++++ explanation. Really appreciate it!
Great, very intuitive and explanative
Awesome explanation, made this complex algo smooth.
Explanation is Awesome !
Amazing explanation man, props to you!
Clean and precise explanation !!
Great walkthrough, thank you!
Awesome man... Nice explanation
Thank you so much. I kept looking at an implementation and had a hard time trying to figure out what was happening. I got it now.
Precise and sweet explanation. thanks :)
Very good explanation!!
Dude, you're awesome. Thank you for these videos.
Explanation was very nice , thanks for the vid :D
You explain very well. Thank you
Very Good Explanation Thanks
Don't you spit whenever you say "t"?
well explained Tushar.. Just one comment for the viewers this Morris approach can be for Pre order traversal also ..and with just 1 line change in the existing code..( let it be a exercise for the viewers)
+Tushar Roy oh !! I had not seen the full video earlier.. yes its there..
For Morris Postorder feel free to take a look at www.thealgorists.com/Algo/Tree/MorrisPostorder . Morris Postorder algorithm and code are beautifully explained there.
Thanks for your hard work for making such nice videos!
But it would be great if the video explains algorithm derived from concept behind it.
What I understand, concpet is the first thing then algo comes. You explan such a way where algo comes first then explain the concept based on the algo! Thank you!
clean algorithm, beautifully explained. thank you so much!
Great explaination!
Why not to use threaded three in the first place?
Awesome! Thank you Tushar!! :D
Thanks so much for making my life easier!!!
Talk about an elegant algorithm.
Can we use this to traverse inorder reversely(right->root->left) ? ig yes ...reply if not
Nice explained♥️
how is the time complexity O(n)... we are revisiting nodes in a loop many times...
Thank you great explanation
good explanation, Sometimes I feel it's really helpful for yourself to understand better by presenting your idea to others
Nice explanation!
very well explained..thank you so much
Nicely explained. Thanks!
Excellent explanation!
That's great explanation!
Thank you for your explanation.
Thank You Tushar.. Nice explanation. It really helped me.
Thank You
I love this guy
why time complexity is O(n)?
really made it easy to understand
could you please make similar videos for Morris traversal for priorder and post order traversal
Nice explanation
Is there any Morris PostOrder algorithm or we need to tweak this technique to achieve postorder?
Morris Postorder Traversal is explained here: www.thealgorists.com/Algo/Tree/MorrisPostorder
predecessor.right will always be null right? Because if a predecessor of a current node has a right child, then that right child is the predecessor of the current node, no?
Nevermind, we need that if statement to see if we establish a link to a "current" node
I've watched this like 10 times xD
very clear, thank you so much
Thanks a lot!
Great explanation
very clear explanation!
Are u using recursion or stack to find inorder predecessor
th-cam.com/video/_AQdLuOvjPw/w-d-xo.html
your videos are awesome Tushar. Great work.
Nice Explanation
very clear thank you so much
Very well explained ... !!!!
Great video! Thanks.
This is much clearer than the explanation on the geekforgeeks channel.
Explanation is excellent , simple request is to talk at steady pace. a bit slower ...then it will be much easier to absorb :)
thanks for the explanation
Please make a video on morris postorder traversal !
Take a look at www.thealgorists.com/Algo/Tree/MorrisPostorder . Morris Postorder algorithm and code are explained there.
Will the algorithm work if we have duplicate elements in the tree?
if you are using Trees to implement map data structure which does not allow duplicate,do not insert the duplicate element at the first place
awesome stuff mate..awesome
nice explanation