Binary Tree Inorder Traversal | Morris Traversal | Leetcode-94

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

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

[lofireverbz-wygo]

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<int> preorderTraversal(TreeNode* root) {
vector<int> 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;
}
};

[Momentsofmagic]

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.

[ugcwithaddi]

You were right, Dry run is one of the most underrated skill.
Thanks a lot legend 🙌🙌🙌

[DevOpskagyaan]

Mast samjhate ho sir aap 🔥🔥🔥
Thanks from my whole college friends and me

[wearevacationuncoverers]

Everyday you teach me something.
Thank you so so much MIK
(Is baar wala Thumbnail mast hai)

[deepakdass]

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 😊😊

[raisanjeeb]

Thank you bhaiya for this wonderful explanation!
Best Explanation for morris order one could find on YouTube ❤

[PintushKumar-nw]

Jaha MIK sir hai waha daily kuchh na kuchh shikhne ko milega

[Tjr]

Better than best one (strivers) both are very helpful

[technologicalvivek]

Bahut badiya samjhate ho bhaiya aap. maza aa jata hai.
bhaiya mein gate 2024 qualify ho gya.

[himanshuvarshney]

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 ❤

[basujain]

bhai striver se jyafa accha padhate ho

[Cpp_Algo]

Thank_you_so_Much sir for your explanation .

[molyoxide]

MIK made it easy henceforth it's MIK Traversal.

[dayashankarlakhotia]

Revise Morris traverse
Thanks again 🎉❤

[rohitshah]

Meanwhile me thinking aaj ke question mai kuch sikhne layak nahi hai

[anushkathakur]

bhaiya aaj ka biweekly contest ka yeh graph ka question please samjha dijiye please....Number of Possible Sets of Closing

[Singh_]

Bhaiya preorder and post order ka bhi code comment me reply kr do please

[suvankar]

Iss logic se pre-order traversal kaise karu bhaiyaa?

[sanjaykatta]

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.