Binary Tree Inorder Traversal | Morris Traversal | Leetcode-94
75Whatsapp Community Link : https://www.whatsapp.com/channel/0029Va6kVSjICVfiVdsHgi1A
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) : https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/Tree/Morris%20Traversal(Binary%20Tree%20Inorder%20Traversal).cpp
Leetcode Link : https://leetcode.com/problems/binary-tree-inorder-traversal/
My DP Concepts Playlist : https://youtu.be/7eLMOE1jnls
My Graph Concepts Playlist : https://youtu.be/5JGiZnr6B5w
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Interview_DS_Algo
Subscribe to my channel : https://www.youtube.com/@codestorywithMIK
Instagram : https://www.instagram.com/codestorywithmik/
Facebook : https://www.facebook.com/people/codestorywithmik/100090524295846/
Twitter : https://twitter.com/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