This channel is literally underrated, I watched Morris Traversal from Striver as well as Love Babbar, but always found it difficult. This tutorial is literally the best explanation on Morris Traversal.
Postorder Traversal vector postOrder(Node* root) { // code here // We will traverse the tree in the order - N R L. vector ans; // We will traverse the tree until our root becomes nuLL that shows we have traverse the whole tree. while(root) { // If right of root doesn't exist then we will just go the left side and push the value of the node into the array. if(!root -> right){ ans.push_back(root -> data); root = root -> left; } // If right of root exist: else { // So if the right exist then we have to: // first, create a link of the leftmost node to the root node. // So that we can come back to root node. Node *curr = root -> right; // We are going to the leftmost node. while(curr -> left && curr -> left != root) curr = curr -> left; // So now there are two conditions: // First, that we have not traverse that right [part. // Second, we have traverse the right part. // Now if we have not traverse the part then the left value of the curr node is NULL. // So we will add the value of the node to the ans array. // And make a link and go the right. if(curr -> left == NULL){ ans.push_back(root -> data); curr -> left = root; root = root -> right; } // If we done the traversal then we will simply remove the link and go to left part. else { curr -> left = NULL; root = root -> left; } } } // After that we will reverse the ans array. reverse(ans.begin(), ans.end()); return ans; }
Morris PostOrder Traversal code vectorans; // store answer while(root){ // check if right substree exits or not if(!root->right){ ans.push_back(root->data); root = root->left; // go to left subtree for further processing } else{ // when left substree exist Node* curr = root->right; // create instance while(curr->left && curr->left != root){ curr = curr->left; } // after reaching last node we connect last node with root node curr->left = root->left; ans.push_back(root->data); root = root->right; // move to right for further processing
//in postorder traversal follow(LEFT-RIGHT-NODE) in i reverse this technique which is (NODE-RIGHT-LEFT) and at end i reverse the all value of array then return: class Solution { public: vector postorderTraversal(TreeNode* root) { vector ans; // Stores result while (root) { //when right child of root node is not exist if (!root->right) { ans.push_back(root->val); root = root->left; } // when right child of root node is exist else { TreeNode* curr = root->right; // Find leftmost node in right subtree while (curr->left && curr->left != root) { curr = curr->left; } // Create link ,when right subtree of root node of left child's left part is null then its in left ptr to link root node for for accesss that element reverse time if (!curr->left) { ans.push_back(root->val); curr->left = root; // Make link root = root->right; } // Remove link,when the work is done that node then link is remove else { curr->left = NULL; // Remove link root = root->left; } } } // Reverse the answer array for to get correct order reverse(ans.begin(), ans.end()); return ans; } };
Using Morris Algorithem T.C->O(n) and S.C->O(1) class Solution{ public: vector postOrder(Node* root) { vectorans; // Post Order -> LRN // Reverse of Post Order -> NRL // Node // Right // Left while(root){ // Rigth part does not exist if(!root->right){ ans.push_back(root->data); root=root->left; } // Right part exist else{ Node *curr=root->right; while(curr->left && curr->left!=root){ curr=curr->left; } //Right subtree not traverse if(curr->left==NULL){ ans.push_back(root->data); curr->left=root; root=root->right; } // Already treverse else{ curr->left=NULL; root=root->left; } } } // NRL reverse to LRN reverse(ans.begin(),ans.end()); return ans; } };
class Solution{ public: vector postOrder(Node* root) { vectorans;vectora; while(root) { // first see if right doesnt exist then simply go to left if(root->right==NULL) {ans.push_back(root->data); root= root->left; } else {//if right exist check if link is present or it the left of node isNULL Node* p = root->right; while(p->left&&p->left!=root) { p = p->left; } //if p->left = null means visiting it for first time so push the answer then create ,link and move the pointer to right if(p->left==NULL) { ans.push_back(root->data); p->left= root; root= root->right; } //if link exist then break the link and move to the left part sice we have traversed the right part else { p->left=NULL; root= root->left; } }
} // reverse the answer for(int i = ans.size()-1;i>=0;i--) { a.push_back(ans[i]); } return a; } };
vector postOrder(Node* root){ vector ans; //At first we will traverse Node,Right & Left in this order.At the end we reverse the vector to get ans. while(root){ //right does not exist if(!root->right){ ans.push_back(root->data); root = root->left; } else{//right exist Node* curr = root->right; while(curr->left && curr->left != root) curr = curr->left; //if not traverse if(!curr->left){ ans.push_back(root->data); curr->left = root; root = root->right; } else{//traversed curr->left = nullptr; root = root->left; } } } reverse(ans.begin(),ans.end());//for getting actual ans return ans; }
class Solution{ public: vector postOrder(Node* root) { // code here vectorans; //post order - LRN // reverse of post order -NRL //NODE //RIGHT //LEFT
// when root exits while(root) { // when right doen't exits if(!root->right) { ans.push_back(root->data); root = root->left; } //when right exits else { Node * curr = root->right; //when right is not traverse while(curr->left && curr->left!=root) { curr = curr->left; } if(curr->left == NULL) { //store the root-> data in ans ans.push_back(root->data); //create link between last right node and root node curr->left = root; //move to right root =root->right; } // when right is already traverse else { curr->left = NULL; root = root->left; } } } //reverse it, in order to make it LRN(postorder) reverse(ans.begin(), ans.end()); return ans; } };
/* STEPS: 1. Right part does not exist: i) note down the data ii) move to left part 2. Right part exist: i)Right subtree is not traversed yet (a) note down the data (b) create link (c) move to the right part ii)Right subtree already traversed (a) remove the link (b) move to the left part */ //Morris Traversal(Space Complexity O(1) and T.C=O(n) ) //left, right, node //1st we solve reverse way: node, right, left vector postOrder(Node* root) { vectorans; while(root){ //right part does not exist if(root->right == NULL){ ans.push_back(root->data); root = root->left; } //right part exist else{ Node *curr = root->right; while(curr->left != NULL && curr->left != root) curr = curr->left; //right subtree is not traversed if(curr->left == NULL){ ans.push_back(root->data); curr->left = root; //create link root = root->right; } //right subtree is already traversed else{ curr->left = NULL; //break the link root = root->left; } } } //Now reverse the answer reverse(ans.begin(), ans.end()); return ans; }
50:18 [Morris Traversal Post order]: void morris_traversal_postorder(Node* root) { if (!root) { return; } // Here stack is just used to store answer, not for traversing purpose // If we used vector then we need to reverse it but in stack we already get last value so print it directly stack ans; while (root) { // Is Right Exist if (root->right) { Node* temp = root->right; // Going extreme left of temp node while (temp->left && temp->left != root) { temp = temp->left; } // If temp node left point to root node means We already traversed it if (temp->left == root) { // remove linked from root to null and move to left temp->left = nullptr; root = root->left; } // We traversed first time so push value in ans stack else { ans.push(root->data); // make linked to root and move right temp->left = root; root = root->right; } } // Right Not Exist means push in ans stack and move to left else { ans.push(root->data); root = root->left; } } // printing traversed value while (!ans.empty()) { int top = ans.top(); ans.pop(); cout
Post Order trivasal By Morris Method class Solution{ public: vector postOrder(Node* root) { // code here // insert NRL then reverse which is LNR is post order vectorans; while(root){ // Right part doesn't exits if(!root->right){ ans.push_back(root->data); root=root->left; } // if right part exist karta ho else{ Node *curr=root->right; while(curr->left&&curr->left!=root){ curr=curr->left; } // right subtree is not trivased if(curr->left==NULL){ ans.push_back(root->data); curr->left=root; root=root->right; } // right subtree is trivased already else{ curr->left=NULL; root=root->left; } } } reverse(ans.begin(),ans.end()); return ans; } };
code for post order: /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector postorderTraversal(TreeNode* root) { // LRN // reverse = NRL vector ans; while(root){ if(root -> right == NULL){ ans.push_back(root -> val); root = root -> left; } else { // right of root exists // so now we go to leftmost node // to check if the link exists or we have to make one TreeNode* curr = root -> right; while(curr -> left != NULL && curr -> left != root){ curr = curr -> left; } if(curr -> left == NULL){ // we have to make the link // first time on that node ans.push_back(root->val); curr -> left = root; root = root -> right; } else if(curr -> left == root){ curr -> left = NULL; // ans.push_back(root -> val); root = root -> left; // since this portion has been already visited } } } reverse(ans.begin(), ans.end()); return ans; } };
// Morris Travesal class Solution{ public: vector postOrder(Node* root) { vectorans; // creating vector for storing the ans while(root){ // we will run while lopp while root will not be null if(root->right==NULL){ // right does't exits ans.push_back(root->data); root = root->left ; }else{ // right exits
{While(root) // to store root {ans.push _back(root->data); // right kr end tak jana aur current ke left mein jana Node*curr=root->right ; {While (root>right =null;&& root>left =null; Curr=curr->left; Curr-left=root ; root=root->left; } else{ Node *cure =root->left}
50:20 Morris Travesal for Post order class Solution { public: /* take this example 1 / \ 2 3 / \ 4 5 (5's left connected to 3) (4's left connected to 1) */ vector postorderTraversal(TreeNode* root) { // L R N -> original // we use morris traversal to find reverse of that 1st then reverse it // N R L // code here vector revPostOrder; TreeNode* curr = root; while(curr != NULL) { // if curr right is null then visit it, then go to left (5 node) if(curr->right == NULL) { revPostOrder.push_back(curr->val); curr = curr->left; } else { // right node is not null (like 1) // 1st find predecessor, then connect the link //a. find predecessor TreeNode* pred = curr->right; while(pred->left != curr && pred->left) { pred = pred->left; } // b. check if the pred is already linked or not if(pred->left == NULL) { pred->left = curr; revPostOrder.push_back(curr->val); curr = curr->right; } else { // disconnect the link then go to left pred->left = NULL; curr = curr->left; } } } reverse(revPostOrder.begin(), revPostOrder.end()); return revPostOrder; } };
Postorder Traversal using Morris Traversal vector result; while(root) { // if right subtree does not exist if(!root->right) { // if root->right is null then store root data into result result.push_back(root->data); // after that move root to the left root = root->left; } // if right subtree exist else { Node* curr = root->right; // run loop until curr->left is null or curr->left is root while(curr->left and curr->left != root) curr = curr->left;
// if curr->left is null that means link is not created, create link // with left most node, store root->data into result, and move root // to its right if(!curr->left) { curr->left = root; result.push_back(root->data); root = root->right; } // if link is created, that means right subtree is already traversed, // thenbreak the link and move root to its left subtree else { curr->left = nullptr; root = root->left; } } } // After that reverse the traversal because postorder traversal say // At first Left subtree, then Right Subtree and then Root, but here I done it // reverse, at first Root, then Right Subtree then Left Subtree. So, result // come in reverse, that's why reverse it reverse(result.begin(), result.end()); return result;
class Solution { public: vector postorderTraversal(TreeNode* root) { vectorans; while(root) {//postorderTraversal(left->right->node) //Node->left->right=>reverse it //right leaf node dont have if(!root->right) { //value le lo or left mai jao ans.push_back(root->val); root=root->left; } else { //root ka right exist hai to root ka //sable leftmost children ko bolo root ko pont kare TreeNode *curr=root->right; while(curr->left&&curr->left!=root) { curr=curr->left; } if(curr->left==NULL) { //ham root ka left children kai leftmost last node pe hai //jo abhi null hai(1 st time ham aa rahe hai) //to root ka data push karo or loop bana do ans.push_back(root->val); curr->left=root; root=root->right; }//ham Traverse kar chuke hai,to wo loop hata do // or left mai jaoo else { curr->left=NULL; root= root->left; } } } reverse(ans.begin(),ans.end()); return ans;
❤🔥 PostOrder: vector postOrder(Node* root) { // code here //for post order (lrn) //but in this case we do NRL //Morris Traversal vectorans; while(root) { //right part does not Exist if(!root->right) { ans.push_back(root->data); root=root->left; } else//right part exist { Node *cur=root->right; while(cur->left&&cur->left!=root) { cur=cur->left; } //right sub tree not traversed if(cur->left==NULL) { ans.push_back(root->data); cur->left=root; root=root->right; } else //alreay traversed { cur->right=NULL; root=root->left; } } } //reverse reverse(ans.begin(),ans.end()); return ans; } };
Bhaiya exam ke karan discontinue hogaya hai will be back soon ❤❤.. i have exam today but still wanted to comment i usually won't most of the times but i do care ur channel a lot❤❤
//code here //WE ARE DOING MORRIS TRAVERSAL /* Acctual Postorder Left Right Node But we do Node Right Left */ vectorans; while(root) { //Right Part doesn't exit if(!root->right) //if (root->right == NULL) { ans.push_back(root->data); root=root->left; } //Right Part exit else{ Node * curr = root->right; while(curr->left && curr->left!=root){ curr=curr->left; } //right subtree not traversal if(curr->left==NULL){ ans.push_back(root->data); curr->left=root; root=root->right; }else{ //Alreay Traversal curr->left=NULL; root=root->left; } } } //Now i will make my answer LRN reverse(ans.begin(),ans.end()); return ans;
PostOrder Traversal vector postOrder(Node* root) { // code here //Morris Traversal vectorans; while(root) { //Right part doesn't exist, Store and Go left if(!root->right) { ans.push_back(root->data); root=root->left; } //Right part exists else { Node *curr=root->right; while(curr->left!=NULL && curr->left!=root) { curr=curr->left; } //Right not traversed, Store and Go right if(curr->left==NULL) { ans.push_back(root->data); curr->left=root; root=root->right; } //Right traversed, Go left else { curr->left=NULL; root=root->left; } } } reverse(ans.begin(), ans.end()); return ans; }
why is it causing problem if we don't remove link as we have already traversed the left subtree and curr has been move to right subtree then it is obvious that we will never visit left subtree then why it is giving runtime error
Preorder Morris Traversal k each left ko right and each right ko left m convert krne se we get --- NODE--RIGHT-LEFT . Later we reverse the answer list and we get LEFT---RIGHT----NODE Our PostOrder Morris Traversal.
Morris Traversal Mein Maja aaya fr💯
bhut maja aaya
❤
❤❤❤❤
This channel is literally underrated, I watched Morris Traversal from Striver as well as Love Babbar, but always found it difficult. This tutorial is literally the best explanation on Morris Traversal.
exactly same situation
same here
Postorder Traversal
vector postOrder(Node* root) {
// code here
// We will traverse the tree in the order - N R L.
vector ans;
// We will traverse the tree until our root becomes nuLL that shows we have traverse the whole tree.
while(root) {
// If right of root doesn't exist then we will just go the left side and push the value of the node into the array.
if(!root -> right){
ans.push_back(root -> data);
root = root -> left;
}
// If right of root exist:
else {
// So if the right exist then we have to:
// first, create a link of the leftmost node to the root node.
// So that we can come back to root node.
Node *curr = root -> right;
// We are going to the leftmost node.
while(curr -> left && curr -> left != root)
curr = curr -> left;
// So now there are two conditions:
// First, that we have not traverse that right [part.
// Second, we have traverse the right part.
// Now if we have not traverse the part then the left value of the curr node is NULL.
// So we will add the value of the node to the ans array.
// And make a link and go the right.
if(curr -> left == NULL){
ans.push_back(root -> data);
curr -> left = root;
root = root -> right;
}
// If we done the traversal then we will simply remove the link and go to left part.
else {
curr -> left = NULL;
root = root -> left;
}
}
}
// After that we will reverse the ans array.
reverse(ans.begin(), ans.end());
return ans;
}
thanks bro
post order using morris traversal
// using morris traversal
class Solution{
public:
vector postOrder(Node* root) {
// code here
vectorans;
while(root){
// left part doesn't exist
if(!root->right){
ans.push_back(root->data);
root=root->left;
}
// left part exist
else{
Node*curr=root->right;
while(curr->left && curr->left!=root)
curr=curr->left;
// left subtree not traverse
if(curr->left==NULL){
ans.push_back(root->data);
curr->left=root;
root=root->right;
}
// already exist
else{
curr->left=NULL;
root=root->left;
}
}
}
reverse(ans.begin(),ans.end());
return ans;
}
};
👍👍acha lage toh 😊
Pehle mene pseudocode likha and badme code implement Kiya.
Post Order Code Done ✅
Literally the best tutorial of Morris Traversal on TH-cam . Thanks sir!
Day 161 ✅🔥
Learning++ bhaiya ✨
// Approach 3 : Morris Traversal : TC:O(n) SC:O(1)
vector postorderTraversal(TreeNode *root)
{
vector ans;
TreeNode *curr = root;
// solving for (NRL)
while (curr)
{
// right doesnt exist, noteNode, goLeft
if (!curr->right)
{
ans.push_back(curr->val);
curr = curr->left;
}
// right exist
else
{
TreeNode *post = curr->right;
// check link
while (post->left && post->left != curr)
post = post->left;
// noLink, notTraversed, createLink, noteNode, goRyt
if (!post->left)
{
post->left = curr;
ans.push_back(curr->val);
curr = curr->right;
}
// Link, Traversed, destroyLink, goLeft
else
{
post->left = NULL;
curr = curr->left;
}
}
}
// reverse ans to get postorder (LRN) from (NRL)
reverse(ans.begin(), ans.end());
return ans;
}
pura chamak gya bhaiya morris traversal pura ache se best explaination...........🤗🤗🤗🤗🤗
Morris PostOrder Traversal code
vectorans; // store answer
while(root){
// check if right substree exits or not
if(!root->right){
ans.push_back(root->data);
root = root->left; // go to left subtree for further processing
}
else{
// when left substree exist
Node* curr = root->right; // create instance
while(curr->left && curr->left != root){
curr = curr->left;
}
// after reaching last node we connect last node with root node
curr->left = root->left;
ans.push_back(root->data);
root = root->right; // move to right for further processing
}
}
reverse(begin(ans) , end(ans));
return ans;
Post Order Traversal:
vector postOrder(Node* node) {
vector ans;
while(node) {
// Right part doesn't exist
if(!node ->right){
ans.push_back(node ->data);
node = node ->left;
}
else { // Right part exist
Node *curr = node ->right;
while(curr ->left && curr ->left != node){
curr = curr ->left;
}
//Right subtree is not traversed yet
if(curr ->left == NULL) {
curr ->left = node;
ans.push_back(node ->data);
node = node ->right;
}
else { //Right subtree already traversed
curr ->left = NULL;
node = node ->left;
}
}
}
reverse(ans.begin(), ans.end());
return ans;
}
maza a gya video dhekh ke learning first time morris traversal
//in postorder traversal follow(LEFT-RIGHT-NODE) in i reverse this technique which is (NODE-RIGHT-LEFT) and at end i reverse the all value of array then return:
class Solution {
public:
vector postorderTraversal(TreeNode* root) {
vector ans; // Stores result
while (root) {
//when right child of root node is not exist
if (!root->right) {
ans.push_back(root->val);
root = root->left;
}
// when right child of root node is exist
else {
TreeNode* curr = root->right;
// Find leftmost node in right subtree
while (curr->left && curr->left != root) {
curr = curr->left;
}
// Create link ,when right subtree of root node of left child's left part is null then its in left ptr to link root node for for accesss that element reverse time
if (!curr->left) {
ans.push_back(root->val);
curr->left = root; // Make link
root = root->right;
}
// Remove link,when the work is done that node then link is remove
else {
curr->left = NULL; // Remove link
root = root->left;
}
}
}
// Reverse the answer array for to get correct order
reverse(ans.begin(), ans.end());
return ans;
}
};
class Solution {
public:
vector postorderTraversal(TreeNode* root) {
vector ans;
while (root) {
if (!root->right) { // right doesn't exist
ans.push_back(root->val);
root = root->left;
} else { // right part exist
TreeNode* curr = root->right;
while (curr->left && curr->left != root) {
curr = curr->left;
}
if (curr->left == NULL) { // right part doesn't traverse
ans.push_back(root->val);
curr->left = root;
root = root->right;
} else { // already traverse
curr->left = NULL;
root = root->left;
}
}
}
reverse(ans.begin(),ans.end());
return ans;
}
};
Thank you for this playlist but just one question is it gonna be a complete one i mean complete DSA using C++?
We solve postorder by reversing the NRL order which will be a mirror NLR i.e preorder , hence the solution will be
vectorans;
while(root){
if(!root->right){
ans.push_back(root->data);
root = root->left;
}
else{
Node *curr = root->right;
while(curr->left && curr->left != root)
curr = curr->left;
if(curr->left == NULL){
ans.push_back(root->data);
curr->left = root;
root = root->right;
}
else{
curr->left = NULL;
root = root->left;
}
}
}
reverse(ans.begin(),ans.end());
return ans;
bhaiya easily understood and chamak gaya sab, thank you bhayia
class Solution{
public:
vector postOrder(Node* node) {
vectorans;
while(node)
{
//right part does not exist
if(!node->right)
{
ans.push_back(node->data);
node=node->left;
}
//right part exist
else
{
Node* curr=node->right;
while(curr->left && curr->left!=node)
curr=curr->left;
//right part not traversed
if(curr->left==NULL)
{
curr->left=node;
ans.push_back(node->data);
node=node->right;
}
//right part traversed
else
{
curr->left=NULL;
node=node->left;
}
}
}
//conversion from NRL to LRN
int start=0,end=ans.size()-1;
while(start
Done Bhaiya... Day 161/180 ✅💯
Post Order Moris traversal:
class Solution{
public:
vector postOrder(Node* root) {
vector ans;
// left , right, node ---> node, right, left
while(root != NULL){
if(root->right == NULL){
ans.push_back(root->data);
root = root->left;
}
else{
Node* temp = root->right;
while(temp->left != nullptr && temp->left != root){
temp = temp->left;
}
// if leftmost of rightpart not visited
if(temp->left == nullptr){
ans.push_back(root->data);
temp->left = root;
root = root->right;
}
// if the leftmost of right part already visited
if(temp->left == root){
temp->left = NULL;
root = root->left;
}
}
}
// To get actual result
reverse(ans.begin(), ans.end());
return ans;
}
};
Best explanation on Morris Traversal ❤
watching your channelf or the first time and i am really impressed.
Using Morris Algorithem T.C->O(n) and S.C->O(1)
class Solution{
public:
vector postOrder(Node* root) {
vectorans;
// Post Order -> LRN
// Reverse of Post Order -> NRL
// Node
// Right
// Left
while(root){
// Rigth part does not exist
if(!root->right){
ans.push_back(root->data);
root=root->left;
}
// Right part exist
else{
Node *curr=root->right;
while(curr->left && curr->left!=root){
curr=curr->left;
}
//Right subtree not traverse
if(curr->left==NULL){
ans.push_back(root->data);
curr->left=root;
root=root->right;
}
// Already treverse
else{
curr->left=NULL;
root=root->left;
}
}
}
// NRL reverse to LRN
reverse(ans.begin(),ans.end());
return ans;
}
};
Very well explained. Enjoyed the video a lot. Thank you so much.
class Solution{
public:
vector postOrder(Node* root) {
vectorans;vectora;
while(root)
{
// first see if right doesnt exist then simply go to left
if(root->right==NULL)
{ans.push_back(root->data);
root= root->left;
}
else
{//if right exist check if link is present or it the left of node isNULL
Node* p = root->right;
while(p->left&&p->left!=root)
{
p = p->left;
}
//if p->left = null means visiting it for first time so push the answer then create ,link and move the pointer to right
if(p->left==NULL)
{
ans.push_back(root->data);
p->left= root;
root= root->right;
}
//if link exist then break the link and move to the left part sice we have traversed the right part
else
{
p->left=NULL;
root= root->left;
}
}
}
// reverse the answer
for(int i = ans.size()-1;i>=0;i--)
{
a.push_back(ans[i]);
}
return a;
}
};
vector postOrder(Node* root){
vector ans;
//At first we will traverse Node,Right & Left in this order.At the end we reverse the vector to get ans.
while(root){
//right does not exist
if(!root->right){
ans.push_back(root->data);
root = root->left;
}
else{//right exist
Node* curr = root->right;
while(curr->left && curr->left != root)
curr = curr->left;
//if not traverse
if(!curr->left){
ans.push_back(root->data);
curr->left = root;
root = root->right;
}
else{//traversed
curr->left = nullptr;
root = root->left;
}
}
}
reverse(ans.begin(),ans.end());//for getting actual ans
return ans;
}
class Solution{
public:
vector postOrder(Node* root) {
// code here
vectorans;
//post order - LRN
// reverse of post order -NRL
//NODE
//RIGHT
//LEFT
// when root exits
while(root)
{
// when right doen't exits
if(!root->right)
{
ans.push_back(root->data);
root = root->left;
}
//when right exits
else
{
Node * curr = root->right;
//when right is not traverse
while(curr->left && curr->left!=root)
{
curr = curr->left;
}
if(curr->left == NULL)
{
//store the root-> data in ans
ans.push_back(root->data);
//create link between last right node and root node
curr->left = root;
//move to right
root =root->right;
}
// when right is already traverse
else
{
curr->left = NULL;
root = root->left;
}
}
}
//reverse it, in order to make it LRN(postorder)
reverse(ans.begin(), ans.end());
return ans;
}
};
/*
STEPS:
1. Right part does not exist:
i) note down the data
ii) move to left part
2. Right part exist:
i)Right subtree is not traversed yet
(a) note down the data
(b) create link
(c) move to the right part
ii)Right subtree already traversed
(a) remove the link
(b) move to the left part
*/
//Morris Traversal(Space Complexity O(1) and T.C=O(n) )
//left, right, node
//1st we solve reverse way: node, right, left
vector postOrder(Node* root) {
vectorans;
while(root){
//right part does not exist
if(root->right == NULL){
ans.push_back(root->data);
root = root->left;
}
//right part exist
else{
Node *curr = root->right;
while(curr->left != NULL && curr->left != root)
curr = curr->left;
//right subtree is not traversed
if(curr->left == NULL){
ans.push_back(root->data);
curr->left = root; //create link
root = root->right;
}
//right subtree is already traversed
else{
curr->left = NULL; //break the link
root = root->left;
}
}
}
//Now reverse the answer
reverse(ans.begin(), ans.end());
return ans;
}
Best explanation of morris traversal you ever find♥ learning++
Thank you so much bhaiya, your explanations are very easy to understand ❤
Nice bhaiya ❤
Keep growing ..
Full support from uttarakhand ❤❤
best lectures on allover youtube
All other youtubers simply ignoring morris postorder without any reason except for u 🙏🙏
Bhaiya Aaj Jo aapne pseudo code likhwaya
Wo acha laga ase hi continue karna
Taki hame aadat ho Jaye uske bad aapko nahi likhne denge 😅😂
Jai Shri Ram ❤️
Thank you Bhaiya 👍🏻
Ek dum op content
Morris PostOrder Just some small changes
vectorans;
//left right rooot
//node right left
while(root)
{
if(!root->right)
{
ans.push_back(root->data);
root=root->left;
}
else
{
//right part not traverse
Node *curr=root->right;
while(curr->left && curr->left!=root)
{
curr=curr->left;
}
//add link
if(curr->left==NULL)
{
ans.push_back(root->data);
curr->left=root;
root=root->right;
}
//already traverse so remove link
else
{
curr->left=NULL;
root=root->left;
}
}
}
reverse(ans.begin(),ans.end());
return ans;
50:20 :
vector postOrder(Node* root) {
// code here
vectorans;
// First we find NRL and then reverse it to get post order
while(root)
{
if(!root->right)//right subtree don't exist
{
ans.push_back(root->data);
root=root->left;//Now move to left subtree
}
else//right subtree exists
{
Node *curr=root->right;
while(curr->left && curr->left != root)
curr=curr->left;
if(!curr->left)//right subtree not traversed
{
ans.push_back(root->data);
curr->left=root;
root=root->right;
}
else // Already traversed
{
curr->left = NULL;
root=root->left;
}
}
}
reverse(ans.begin(),ans.end());//reverse to get LRN
return ans;
}
50:18 [Morris Traversal Post order]:
void morris_traversal_postorder(Node* root) {
if (!root) {
return;
}
// Here stack is just used to store answer, not for traversing purpose
// If we used vector then we need to reverse it but in stack we already get last value so print it directly
stack ans;
while (root) {
// Is Right Exist
if (root->right) {
Node* temp = root->right;
// Going extreme left of temp node
while (temp->left && temp->left != root) {
temp = temp->left;
}
// If temp node left point to root node means We already traversed it
if (temp->left == root) {
// remove linked from root to null and move to left
temp->left = nullptr;
root = root->left;
}
// We traversed first time so push value in ans stack
else {
ans.push(root->data);
// make linked to root and move right
temp->left = root;
root = root->right;
}
}
// Right Not Exist means push in ans stack and move to left
else {
ans.push(root->data);
root = root->left;
}
}
// printing traversed value
while (!ans.empty()) {
int top = ans.top();
ans.pop();
cout
Post Order trivasal By Morris Method
class Solution{
public:
vector postOrder(Node* root) {
// code here
// insert NRL then reverse which is LNR is post order
vectorans;
while(root){
// Right part doesn't exits
if(!root->right){
ans.push_back(root->data);
root=root->left;
}
// if right part exist karta ho
else{
Node *curr=root->right;
while(curr->left&&curr->left!=root){
curr=curr->left;
}
// right subtree is not trivased
if(curr->left==NULL){
ans.push_back(root->data);
curr->left=root;
root=root->right;
}
// right subtree is trivased already
else{
curr->left=NULL;
root=root->left;
}
}
}
reverse(ans.begin(),ans.end());
return ans;
}
};
code for post order:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector postorderTraversal(TreeNode* root) {
// LRN
// reverse = NRL
vector ans;
while(root){
if(root -> right == NULL){
ans.push_back(root -> val);
root = root -> left;
}
else {
// right of root exists
// so now we go to leftmost node
// to check if the link exists or we have to make one
TreeNode* curr = root -> right;
while(curr -> left != NULL && curr -> left != root){
curr = curr -> left;
}
if(curr -> left == NULL){
// we have to make the link
// first time on that node
ans.push_back(root->val);
curr -> left = root;
root = root -> right;
}
else if(curr -> left == root){
curr -> left = NULL;
// ans.push_back(root -> val);
root = root -> left;
// since this portion has been already visited
}
}
}
reverse(ans.begin(), ans.end());
return ans;
}
};
Haan Ji Mere Aaka Good Morning ❤
thanks bhaiya for providing such incredible content
// Morris Travesal
class Solution{
public:
vector postOrder(Node* root) {
vectorans; // creating vector for storing the ans
while(root){ // we will run while lopp while root will not be null
if(root->right==NULL){ // right does't exits
ans.push_back(root->data);
root = root->left ;
}else{ // right exits
Node* curr = root->right; // going from the right to leftmost node
while(curr->left && curr->left !=root){
curr = curr->left;
}
if(curr->left==NULL){ // not travese
curr->left = root;
ans.push_back(root->data);
root = root->right;
}else{ // travesed
curr->left = NULL;
root = root->left;
}
}
}
reverse(ans.begin(),ans.end()); // NRL reverse == LRN(postorder)
return ans;
}
};
Best explanation on internet
# learning++
learning++
vector postorderMorris(Node* root){
vector ans;
Node* curr = root;
while(curr){
if(curr->right){
Node* temp = curr->right;
while(temp->left && temp->left != curr) temp = temp->left;
if(!temp->left){
ans.push_back(curr->data);
temp->left = curr;
curr = curr->right;
}else if(temp->left == curr){
temp->left = NULL;
curr = curr->left;
}
}else{
ans.push_back(curr->data);
curr = curr->left;
}
}
reverse(ans.begin(), ans.end());
return ans;
}++
Rohit Bhaiya teaching dsa >> any paid course 😎
{While(root)
// to store root
{ans.push _back(root->data);
// right kr end tak jana aur current ke left mein jana
Node*curr=root->right ;
{While (root>right =null;&& root>left =null;
Curr=curr->left;
Curr-left=root ;
root=root->left;
}
else{
Node *cure =root->left}
50:20
Morris Travesal for Post order
class Solution {
public:
/*
take this example
1
/ \
2 3
/ \
4 5 (5's left connected to 3)
(4's left connected to 1)
*/
vector postorderTraversal(TreeNode* root) {
// L R N -> original
// we use morris traversal to find reverse of that 1st then reverse it
// N R L
// code here
vector revPostOrder;
TreeNode* curr = root;
while(curr != NULL) {
// if curr right is null then visit it, then go to left (5 node)
if(curr->right == NULL) {
revPostOrder.push_back(curr->val);
curr = curr->left;
} else {
// right node is not null (like 1)
// 1st find predecessor, then connect the link
//a. find predecessor
TreeNode* pred = curr->right;
while(pred->left != curr && pred->left) {
pred = pred->left;
}
// b. check if the pred is already linked or not
if(pred->left == NULL) {
pred->left = curr;
revPostOrder.push_back(curr->val);
curr = curr->right;
} else {
// disconnect the link then go to left
pred->left = NULL;
curr = curr->left;
}
}
}
reverse(revPostOrder.begin(), revPostOrder.end());
return revPostOrder;
}
};
{
Learning ++:
Concepts = Concepts+1;
}
Postorder Traversal using Morris Traversal
vector result;
while(root)
{
// if right subtree does not exist
if(!root->right)
{
// if root->right is null then store root data into result
result.push_back(root->data);
// after that move root to the left
root = root->left;
}
// if right subtree exist
else
{
Node* curr = root->right;
// run loop until curr->left is null or curr->left is root
while(curr->left and curr->left != root)
curr = curr->left;
// if curr->left is null that means link is not created, create link
// with left most node, store root->data into result, and move root
// to its right
if(!curr->left)
{
curr->left = root;
result.push_back(root->data);
root = root->right;
}
// if link is created, that means right subtree is already traversed,
// thenbreak the link and move root to its left subtree
else
{
curr->left = nullptr;
root = root->left;
}
}
}
// After that reverse the traversal because postorder traversal say
// At first Left subtree, then Right Subtree and then Root, but here I done it
// reverse, at first Root, then Right Subtree then Left Subtree. So, result
// come in reverse, that's why reverse it
reverse(result.begin(), result.end());
return result;
class Solution {
public:
vector postorderTraversal(TreeNode* root) {
vectorans;
while(root)
{//postorderTraversal(left->right->node)
//Node->left->right=>reverse it
//right leaf node dont have
if(!root->right) {
//value le lo or left mai jao
ans.push_back(root->val);
root=root->left;
}
else {
//root ka right exist hai to root ka
//sable leftmost children ko bolo root ko pont kare
TreeNode *curr=root->right;
while(curr->left&&curr->left!=root) {
curr=curr->left;
}
if(curr->left==NULL) {
//ham root ka left children kai leftmost last node pe hai
//jo abhi null hai(1 st time ham aa rahe hai)
//to root ka data push karo or loop bana do
ans.push_back(root->val);
curr->left=root;
root=root->right;
}//ham Traverse kar chuke hai,to wo loop hata do
// or left mai jaoo
else {
curr->left=NULL;
root= root->left;
}
}
}
reverse(ans.begin(),ans.end());
return ans;
❤🔥
PostOrder:
vector postOrder(Node* root) {
// code here
//for post order (lrn)
//but in this case we do NRL
//Morris Traversal
vectorans;
while(root)
{
//right part does not Exist
if(!root->right)
{
ans.push_back(root->data);
root=root->left;
}
else//right part exist
{
Node *cur=root->right;
while(cur->left&&cur->left!=root)
{
cur=cur->left;
}
//right sub tree not traversed
if(cur->left==NULL)
{
ans.push_back(root->data);
cur->left=root;
root=root->right;
}
else //alreay traversed
{
cur->right=NULL;
root=root->left;
}
}
}
//reverse
reverse(ans.begin(),ans.end());
return ans;
}
};
38:20 Morris Traversal Pseudo cod for in-Order for revision.
Bhaiya exam ke karan discontinue hogaya hai will be back soon ❤❤.. i have exam today but still wanted to comment i usually won't most of the times but i do care ur channel a lot❤❤
Good luck for exam bhai
@@CoderArmy9Acha Gaya bhai❤❤ abi do bache Hain par firbhi may aajse lecture continue karoonga🤞
void flatten(Node *root){
while(root){
if(root->left){
Node *curr=root->left;
while(curr->right)
curr=curr->right;
curr->right=root->right;
root->right=root->left;
root->left=NULL;
}
root=root->right;
}
}
Bhaiya minimum time to burn a tree???
Rohit bhaiya
What will be your upcoming course??
class Solution{
public:
vector preOrder(Node* root)
{
vectorans;
while(root){
if(!root->left){
ans.push_back(root->data);
root=root->right;
}
else{
Node* curr=root->left;
while(curr->right && curr->right!=root){
curr=curr->right;
}
if(curr->right==NULL){
ans.push_back(root->data);
curr->right=root;
root=root->left;
}
else{
curr->right=NULL;
root=root->right;
}
}
}
return ans;
}
};
ekdam chamak gaya bhaiya
wonderful explanation
//code here
//WE ARE DOING MORRIS TRAVERSAL
/*
Acctual Postorder
Left
Right
Node
But we do
Node
Right
Left
*/
vectorans;
while(root)
{
//Right Part doesn't exit
if(!root->right) //if (root->right == NULL)
{
ans.push_back(root->data);
root=root->left;
}
//Right Part exit
else{
Node * curr = root->right;
while(curr->left && curr->left!=root){
curr=curr->left;
}
//right subtree not traversal
if(curr->left==NULL){
ans.push_back(root->data);
curr->left=root;
root=root->right;
}else{
//Alreay Traversal
curr->left=NULL;
root=root->left;
}
}
}
//Now i will make my answer LRN
reverse(ans.begin(),ans.end());
return ans;
Learning++ bhaiya 🎉
Keep Going
*CODE FOR LAST QUESTION BINARY TO DOUBLY LINKED LIST*
class Solution
{
public:
//Function to convert binary tree to doubly linked list and return it.
Node * bToDLL(Node *root)
{
vector answer;
while(root)
{
if(root->left==nullptr)
{
answer.push_back(root->data);
root=root->right;
}
else
{
Node * current = root->left;
while(current->right && current->right!=root)
{
current=current->right;
}
if(current->right==nullptr)
{
current->right=root;
root=root->left;
}
else
{
current->right =nullptr;
answer.push_back(root->data);
root=root->right;
}
}
}
Node * dummy = new Node(-1);
Node * head=dummy;
for(int i=0;iright = temp;
temp->left=head;
head=head->right;
}
dummy->right->left=nullptr;
return dummy->right;
}
};
PostOrder Traversal
vector postOrder(Node* root) {
// code here
//Morris Traversal
vectorans;
while(root)
{
//Right part doesn't exist, Store and Go left
if(!root->right)
{
ans.push_back(root->data);
root=root->left;
}
//Right part exists
else
{
Node *curr=root->right;
while(curr->left!=NULL && curr->left!=root)
{
curr=curr->left;
}
//Right not traversed, Store and Go right
if(curr->left==NULL)
{
ans.push_back(root->data);
curr->left=root;
root=root->right;
}
//Right traversed, Go left
else
{
curr->left=NULL;
root=root->left;
}
}
}
reverse(ans.begin(), ans.end());
return ans;
}
post order traversal code.............
class Solution{
public:
vector postOrder(Node* root) {
//use NRL concept
//node
//left
//right
vectorv;
while(root)
{
//if root's right part is not exist
if(!root->right)
{
v.push_back(root->data);
root=root->left;
}
//if root's right part is exist
else
{
Node * curr=root->right;
while(curr->left && curr->left!=root)
{
curr=curr->left;
}
//right subtree traverse or not
//if not traverse
if(curr->left==NULL)
{
v.push_back(root->data);
curr->left=root;
root=root->right;
}
//if traverse
else
{
curr->right=NULL;
root=root->left;
}
}
}
reverse(v.begin(),v.end());
return v;
}
};
why is it causing problem if we don't remove link as we have already traversed the left subtree and curr has been move to right subtree then it is obvious that we will never visit left subtree then why it is giving runtime error
Good morning bhaiya ji. 💖
Post-order.
class Solution{
public:
vector postOrder(Node* node) {
// code here
vectorans;
//node
//right
//left
while(node)
{
if(!node->right) // If right does not exist
{
ans.push_back(node->data);
node=node->left;
}
else //If right exist
{
Node *curr = node->right ;//pointer pointing to right node of the root
while(curr->left && curr->left!=node)
{
curr=curr->left;
}
//right subtree not traversed
if(curr->left == NULL)
{
ans.push_back(node->data);
curr->left = node;
node=node->right;
}
else //right subtree is traversed
{
curr->left = NULL;
node=node->left;
}
}
}
reverse(ans.begin(),ans.end());
return ans;
}
};
Chamak gyaa bhejii❤❤❤
bhot badhiya bhaiya
solution of postorder traversal using morris traversal
vectorans;
while(root){
// if right node does not exist
if(!root->right){
ans.push_back(root->data);
root = root->left;
}
// if right node exist
else{
Node*temp= root->right;
while(temp->left && (temp->left!=root)){
temp = temp->left;
}
// if left subtree does not traverse
if(temp->left==NULL){
ans.push_back(root->data);
temp->left = root;
root = root->right;
}
//if left subtree exist
else{
temp->left = NULL;
root =root->left;
}
}
}
reverse(ans.begin(),ans.end());
return ans;
End tak
Preorder Morris Traversal k each left ko right and each right ko left m convert krne se we get --- NODE--RIGHT-LEFT . Later we reverse the answer list and we get LEFT---RIGHT----NODE
Our PostOrder Morris Traversal.
postorder solution --
class Solution{
public:
vector postOrder(Node* node) {
// code here
vectorans;
while(node){
if(!node->right){
ans.push_back(node->data);
node=node->left;
}else
{
Node *curr=node->right;
while(curr->left&&curr->left!=node){
curr=curr->left;
}
if(curr->left==NULL){
ans.push_back(node->data);
curr->left=node;
node=node->right;
}else {
curr->left=NULL;
node=node->left;
}
}
}reverse(ans.begin(),ans.end());
return ans;
}
};
Haaan bhaiya chamak gya
Good morning bhaiya.
Day 161/180 👍👍
Bhaiya Mid Term Aagaye the Issliye Lectures Pending the Ab Cover Ho jayenge 👍
hukum aapka hukm sar aakho per
Day 161/180 #180DaysOfCode
Bhaiya Radhe Radhe 🙏
Radhe Radhe bhai
Impressive
bhaiya learning++
chamak gya bhaiya
learning ++ thanks
Chamak gya bhaiya
Thanks Bhaiya...❤🎉
Like kar diya bhai
Learning++
Bhaiya radhe radhe 🙏🏻🙏🏻
Name Vijay singh NEXUS and DSA both i will do and get the placement in future ❤
Learning++ bhaiya
Bhaut badiya
good morning bhaiya ji
Dsa notes me page no 35 me.
Num=0;
Cout
Bhaiyya..agar 180 days ho gaye...toh aap DSA bandh kar denge kya ?? Kyuki bohot contents baaki hai
Learning ++ 😉
maza aa gya..
Bhaiya best of best❤
vector postorderTraversal(TreeNode* root) {
//morris traversal
//time O(n) space O(1)
//intution is reverse of NRL
vector ans;
while(root){
if(!root->right) {
ans.push_back(root->val);
root=root->left;
}
else{
TreeNode* temp = root->right;
while(temp->left && temp->left != root) temp=temp->left;
if(!temp->left){ //right side is not traversed
temp->left = root;
ans.push_back(root->val);
root=root->right;
}
else{ //right side is traversed
temp->left = NULL;
root=root->left;
}
}
}
reverse(ans.begin(), ans.end());
return ans;
}
learning++ ❣❣