Binary Tree Inorder Traversal | Morris Traversal | Leetcode-94
Vložit
- čas přidán 5. 09. 2024
- Whatsapp Community Link : www.whatsapp.c...
This is the 33rd Video of our Binary Tree Playlist.
In this video we will try to solve an easy problem Inorder Traversal using Morris Traversal - Binary Tree Inorder Traversal (Leetcode -94).
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Binary Tree Inorder Traversal
Company Tags : Lots of companies
My solutions on Github(C++ & JAVA) : github.com/MAZ...
Leetcode Link : leetcode.com/p...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My GitHub Repo for interview preparation : github.com/MAZ...
Subscribe to my channel : / @codestorywithmik
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Approach Summary :
The given code implements an in-order traversal of a binary tree without using recursion or additional space for a stack. It employs Morris Traversal, a space-efficient algorithm that modifies the structure of the tree temporarily during the traversal.
The main idea is to establish a temporary link between a node and its in-order predecessor by threading some of the null pointers in the tree. The algorithm iterates through the tree, adding nodes to the result vector in the correct order. If a node has a left child, it finds the rightmost node in its left subtree, connects it to the current node, and then moves to the left child. This process continues until a node with no left child is encountered, at which point it is added to the result, and traversal moves to the right child. The process is repeated until the entire tree is traversed in an in-order fashion.
This Morris Traversal approach allows for in-order traversal with O(1) space complexity, making it particularly useful in situations where minimizing space usage is crucial.
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
✨ Timelines✨
00:00 - Introduction
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa
Finally Morris Traversal. Thanks MIK
in case agr kisi ko preorder ka code chaiye to than
only minor change in same format only 2 line change
class Solution {
public:
vector preorderTraversal(TreeNode* root) {
vector result;
TreeNode* curr = root;
while (curr!=NULL) {
if (curr->left ==NULL) {
result.push_back(curr->val);
curr = curr->right;
} else {
TreeNode* leftchild = curr->left;
while (leftchild->right!=NULL) {
leftchild=leftchild->right;
}
leftchild->right = curr->right; // right last node ko current ke right se jodo kuuki humne curr ko print kra lia hai i,e preorder
TreeNode* temp = curr;
result.push_back(curr->val); // connection break krne se phle curr ko store krlo
curr = curr->left;
temp->left = NULL;
}
}
return result;
}
};
bro can you tell for this traversal why this thing is required temp->left = NULL;
because we are pointing to the right of curr, so no matter we have left pointer to the curr we won't go to that node we will move to its right node.
@@word___addict8768 if you don't make temp->left=NULL than for practical thing draw a tree
than if you go left of the tree and when you reach at left's NULL than than it will send curr to right and now you start traversing than again curr will have option to go to left and jabki aisa nhi hona chaiye kuuki tumne usse answer mai daaldia and infinite loop mai fasjaega
I hope you understand now, sorry for late reply
The comments on your videos are clear proof how good you are. You are undoubtedly one of most influential and amazing tutors I have ever seen.
You were right, Dry run is one of the most underrated skill.
Thanks a lot legend 🙌🙌🙌
Jaha MIK sir hai waha daily kuchh na kuchh shikhne ko milega
🙏🙏❤️❤️
Mast samjhate ho sir aap 🔥🔥🔥
Thanks from my whole college friends and me
Everyday you teach me something.
Thank you so so much MIK
(Is baar wala Thumbnail mast hai)
Better than best one (strivers) both are very helpful
Thanks for teaching this concept sir. Although this technique is not using space, but it manipulates the tree itself. That's only the problem ig. But no problem when manipulation is allowed.
Thanks a lot sir 😊😊
Yes you are absolutely right 😇🙏❤️
Thank you for watching 🙏
Thank you bhaiya for this wonderful explanation!
Best Explanation for morris order one could find on CZcams ❤
You are most welcome 😇🙏❤️
Liked the explanation ❤
bhai striver se jyafa accha padhate ho
Bahut badiya samjhate ho bhaiya aap. maza aa jata hai.
bhaiya mein gate 2024 qualify ho gya.
Thank you ❤️
And congratulations brother. Proud moment 😇❤️
Mene babbar bhaiya se iska lecture dekha tha ...aisa lg rha tha ratlo baat khtm ...babbar bhaiya be like --(hmare yha aise hi hota h))😂😂
Aaj jaakr samj aaya kya kar rhe h kyu kar rhe h thanks brother ❤
So far the best video omn this topic
it is very clear now, thanks a lot
Thank_you_so_Much sir for your explanation .
bhai kya samjhaya h yr gjb
Meanwhile me thinking aaj ke question mai kuch sikhne layak nahi hai
lol same 😅
Me too 🤣
MIK made it easy henceforth it's MIK Traversal.
Yeahhh 🔥🔥
Other's praise babbar or Striver for their videos but I don't like their solution because they don't explain in lay man terms like striver( with poor english and fast pace) just completes the solution code anyhow whereas babbar does not have a proper way of teaching so I feel this guy will have a better base as he explains well.
Revise Morris traverse
Thanks again 🎉❤
❤❤
amazing explanation
It helped mem a lot , tysm sir
Most welcome 😊
Great video 👌🏻
Amazing ❤❤
amazing🙃
bhaiya aaj ka biweekly contest ka yeh graph ka question please samjha dijiye please....Number of Possible Sets of Closing Branches.....
Let me check soon
0:07 Hamarey liye sub kathin h 😅🤣, aap pudhao brother 😇
can u please modify the same code to do preorder and post order. If yes how?
Bhaiya preorder and post order ka bhi code comment me reply kr do please
Iss logic se pre-order traversal kaise karu bhaiyaa?
void morrisTraversalPreorder(node* root)
{
while (root)
{
// If left child is null, print the current node data. Move to
// right child.
if (root->left == NULL)
{
coutright && current->right != root)
current = current->right;
// If the right child of inorder predecessor already points to
// this node
if (current->right == root)
{
current->right = NULL;
root = root->right;
}
// If right child doesn't point to this node, then print this
// node and make right child point to this node
else
{
cout
@@EB-ot8uu No I found this one, but sir ne jis logic se bataya uss logic se pre-order and postorder kaise hoga??
@@suvankar54 slight modification from inorder code will get a preorder
void morisPreorder(TreeNode* root, vector &ans)
{
TreeNode * curr = root;
while(curr != NULL)
{
if(curr->left == NULL)
{
ans.push_back(curr->val);
curr = curr->right;
}
else
{
ans.push_back(curr->val);
TreeNode *childNode = curr->left;
while(childNode->right != NULL)
{
childNode = childNode->right;
}
// instead of cur , point to curr->right , this is change from inorder to preorder change .
childNode->right = curr->right;
TreeNode *temp = curr;
curr = curr->left;
// set temp->right to NULL , in inorder temp->left was set to NULL .
temp->right = NULL;
}
}
Bro, will the system's stack be counted while calculating the space complexity? Because I see that when I submitted using the recurisve approach - the space used was less (very minute difference though) compared to the morris traversal.
Update : same code submission on leetcode shows different space complexity on each submission. Not sure why this happens.
On submitting again - I see that morris traversal took less space.
Ya actually it happens. It’s something with leetcode servers behind the scene.
Sir, ye to GOLD hai
if(root != NULL){
inorderTraversal(root->left);
ans.push_back(root->val);
inorderTraversal(root->right);
}
return ans;
Bhai tumne tree modify kr dia h. Ye sahi nhi h. Leetcode me pass hojayega but this is not acceptable in interviews.
Definitely. It’s not acceptable in interviews.
This video is only for the purpose of Teaching Morris Traversal. ❤️
Only if the interviewer allows you to modify the tree, then only apply morris else not.
@@codestorywithMIK Agree with the first part, but as for the second, we can actually write morris traversal to preserve the original tree structure. See Striver's solution for the same.
Anyways, this video is also great! Thanks.
Definitely. Thank you for your valuable feedback 😇❤️
I'm just amazed by his explanation. He's truly a gem, so underrated @codestorywithMK