L12. Iterative Postorder Traversal using 1 Stack | C++ | Java | Binary Trees

[@takeUforward]

This topic is bit tricky, so try to dry run some trees. Its kinda algorithm that you need to remember. Cannot help 😫 Rest all topics are intuitive.. Please likeeee, shareeee and subscribeeeeeeee :) Also follow me at Insta: Striver_79

[@sehejwahla5437]

thanx for this comment.

[@worldfromhome4033]

Thanks for telling because I was worried as it was not intuitive

[@traymk]

Thanks for commenting this

[@huungryyyy]

Thnku for thiss😁😁

[@mohammedaffann]

one more way of using 1 stack would be, in the previous 2 stack video, instead of using 2nd stack we can push into ans. And in the end, we can reverse ans.

[@SadhanaSharma]

yesss! thankss

[@darkexodus6404]

Simply clever.

[@amit2194]

thanks man

[@codewithnoob160]

indeed

[@divyanshjaiswal6964]

Yes you are absolutely correct but in doing so Your time complexity will increase on the other hand to O(nlogn)

[@anmolswarnkar7707]

This just makes you appreciate the "magic" of recursion lol.

[@himalayagupta7744]

++, without recursion we are doomed.

[@demonslayer4607]

How?

[@himalayagupta7744]

@@demonslayer4607 first year ???

[@himalayagupta7744]

@@demonslayer4607 recursion is superpower, treat it as one

[@demonslayer4607]

@@himalayagupta7744 how bro u r so comfortable with recursion? Please give tips bro

[@krishnasudan3410]

I have thought a better approach with same O(2N) TC and O(N) space. Postorder is : Left Right Root Reverse Postorder is: Root Right Left Try Finding Reverse Postorder like preorder using one stack O(N) time and O(N) space Then reverse the resultant vector, that will be the answer O(N) time Overall O(2N) time and O(N) space Code Below: vector postorderTraversal(TreeNode* root) { vector res; if(!root) return res; stack s; s.push(root); while(!s.empty()){ TreeNode* temp = s.top(); s.pop(); res.push_back(temp->val); if(temp->left) s.push(temp->left); if(temp->right) s.push(temp->right); } reverse(res.begin(),res.end()); return res; } Like if it helped you.

[@AnandSharma-lt8wq]

// TC: O(2n) AUX: O(H) // little more optimised ArrayList postOrder(Node node) { ArrayDeque st = new ArrayDeque(); ArrayList al = new ArrayList(); Node curr = node; while(curr!=null || !st.isEmpty()){ while(curr!=null){ al.add(curr.data); if(curr.left!=null) st.push(curr.left); curr=curr.right; } curr= st.poll(); } Collections.reverse(al); return al; }

[@dhruvbhatnagar4999]

Thanks mate!

[@adithyab967]

Appreciate it

[@Dinesh_Dumka]

But it will not work always

[@turjobennington1677]

the best solution I found in LC vector postOrder(Node* node) { vectorans; stackst; st.push({node,false}); while(!st.empty()){ Node*curr=st.top().first; bool isDone=st.top().second; if(isDone){ ans.push_back(curr->data); st.pop(); } else{ st.top().second=true; if(curr->right)st.push({curr->right,false}); if(curr->left)st.push({curr->left,false}); } } return ans; }

[@sandeepdas1883]

Forget about the source codes, these dry runs are so amazing that they have made life so easy for me 😎😋

[@rabindrapatra7151]

use intellij

[@niteshkhanna690]

kaha job kar rahe fir abhi ?

[@player-te8tf]

Kuddos to your hardwork in the recursion videos, the way you used to make function blocks for each recursive calls is what helping me to visualise and grasp the concepts.

[@rishabhtiwari7380]

it can be also simply done like we did in pre-order , but in this we have to push first left child then right child,also we store values in the final array from end! Thankyou for this wonderful dry run.

[@kushalloya4640]

can you elaborate this please??

[@subhajitdey135]

A little note to each bit of code in this traversal : vector postOrder(Node* root) { // Your code here vectorpostorder; if(!root) return postorder; Node* curr=root; stackst; while(!st.empty() || curr){ if(curr){ // if the left exists simply put the left in the stack as in postorder left comes first st.push(curr); curr=curr->left; } else{ Node* temp=st.top()->right; // if temp is null that means the left and right of the st.top() node is already done, time to push it in the vector if(!temp){ temp=st.top(); st.pop(); postorder.push_back(temp->data); // if the current temp is right of st.top() and there is no left present for st.top() (thats why temp==st.top()->right )simply push it in the vector as there is no left present. while(!st.empty() && temp==st.top()->right){ temp=st.top(); st.pop(); postorder.push_back(temp->data); } } // this while loop handles this area : 4 \ 5 \ 6 else curr=temp; } } return postorder; } Hope this could help someone understand better

[@AbhishekAnand-vg2tm]

really helped kudos brother.

[@tusharsinghal1333]

we can just follow the procedure of 2 stacks but replacing the functionality of the 2nd stack with the container vector itself and then at the end we can reverse the vector before returning it. Not aware if this would have any efficiency tradeoffs but does the job with a single stack.

[@ka_ka3141]

absolutely correct

[@vivekthakur6686]

Yes

[@kunalgoel9608]

Yeah Just coded it in java

[@harshgupta958]

Great but If interviewer asked to print instead of storing in a vector then, this approach will be costly.

[@adityaaditya7286]

Technically that is also a stack.. What if interviewer would say print rather than store in vector

[@605_samikrdas4]

i assure you this is quite a tricky one, but what an explanation man !

[@nitingupta1417]

we can do it this way as well: post order is left->right->root; Do traversal in this way--> a kind of preorder root->right->left reverse the result reverseOf(root->right->left) == left->right->root (here you got your postorder) vector postorderTraversal(TreeNode* root) { stacks; if(!root)return {}; s.push(root); vectorv; while(s.size()>0){ TreeNode*node=s.top(); v.push_back(node->val); s.pop(); if(node->left){ s.push(node->left); } if(node->right){ s.push(node->right); } } reverse(v.begin(),v.end()); return v; }

[@rahulsaw8838]

#include using namespace std; class Node { public: int data; Node*left; Node*right; Node(int val) { data = val; left = NULL; right = NULL; } }; Node*buildTree() { int n; cin >> n; if (n == -1) { return NULL; } Node*root = new Node(n); root->left = buildTree(); root->right = buildTree(); return root; } void postOrder(Node*root) { if (!root)return ; postOrder(root->left); postOrder(root->right); cout data left) { continue; } st.push({{st.top().first->left}, {0, 0}}); } else if (!st.top().second.second ) { st.top().second.second = 1; if (!st.top().first->right) { continue; } st.push({{st.top().first->right}, {0, 0}}); } else { cout data

[@psibarpsi]

Wow! That's a cool idea! I wonder why I couldn't come-up with it. Good job, lad! I wonder, though, if they would like such an approach in an interview.

[@chetanraghavv]

Amazing! But I wonder whether this approach will be accepted in interview, because at the end of day, you are traversing the tree in root->right->left fashion, which is not post-order. But still answer is coming correct because we are just printing the reverse of it! Quite clever, if you ask me! 😄

[@noone-fl1qb]

Thats the main issue u are using O(nlogn) time for something that can be solved in O(N) time this is correct but definitely not optimal.

[@saisardesai5548]

@@noone-fl1qb how its O(nlogn) ?

[@AdityaKumar-be7hx]

Solution inspired from the 2 stack solution. The second stack is basically used for storing the answer in reverse. We don't really need that. class Solution { public: vector postorderTraversal(TreeNode* root) { vector preorder; stack st; st.push(root); while(!st.empty()){ auto curr = st.top(); st.pop(); // post order = left, right, root // reverse is root, right, left if(curr!=nullptr){ preorder.push_back(curr->val); st.push(curr->left); st.push(curr->right); } } reverse(preorder.begin(), preorder.end()); return preorder; } };

[@bhavkushwaha]

Was difficult to follow in one go, but rewatching some portions helped in understanding. Thankyou Striver!

[@averylazyandweirdhuman]

Nice Striver! But your graph series feels more interactive because of your gestures and emphasis on important things. Also, the cursor is larger so I could easily see where are you pointing while dry running the code. Above all, Thank you for the series, it takes a lot of time to shoot, edit and handle the job at the same time and with such consistency it's really commendable. And you're really taking us forward and strive for better. 💫

[@anupamtiwary4265]

modifying 2 stack approach . this works too. vector postorderTraversal(TreeNode* root) { vectorpreorder; if(!root) return preorder; stacks1,s2; s1.push(root); while(!s1.empty()){ TreeNode *temp = s1.top(); s1.pop(); preorder.push_back(temp->val); if(temp->left) s1.push(temp->left); if(temp->right) s1.push(temp->right); } reverse(preorder.begin(),preorder.end()); return preorder;

[@shubham8941]

vector postOrder(Node* node) { stack st1; st1.push(node); vector ans; if(!node) return ans; while(!st1.empty()){ node=st1.top(); ans.push_back(node->data); st1.pop(); if(node->left) st1.push(node->left); if(node->right) st1.push(node->right); } reverse(begin(ans),end(ans)); return ans; }

[@rajkr5446]

We can use the previous video concept, but instead of the second stack we can use the ans vector itself and when returning just reverse it. vector postorderTraversal(TreeNode* root) { vector ans; if(root == NULL) return ans; stack st; st.push(root); while(!st.empty()) { TreeNode* node = st.top(); st.pop(); ans.push_back(node->val); if(node->left != NULL) st.push(node->left); if(node->right != NULL) st.push(node->right); } reverse(ans.begin(), ans.end()); return ans; }

[@SushantKumarGond]

one more way of using 1 stack would be, in the previous 2 stack video, instead of using 2nd stack we can push into ans. And in the end, we can reverse ans. vector postorderTraversal(TreeNode* root) { ios::sync_with_stdio(false); cin.tie(nullptr); vectorans; if(root==NULL) return ans; stackst; st.push(root); while(!st.empty()) { TreeNode* first=st.top(); st.pop(); if(first->left!=NULL) st.push(first->left); if(first->right!=NULL) st.push(first->right); ans.push_back(first->val); } reverse(ans.begin(),ans.end()); return ans; }

[@MYANASANTHOSHINI]

Striver thank you so much without looking at the intuition I was able to crack the logic all because of you thank you so much

[@closer9689]

My Approach to this Question is very different....I am storing a pair 0f {Node*,StatusValue} in the stack instead of {Node*}, Here statusValue tells whether the the currNode's entire left and right subtree has been visited or not. For this , If statusValue = 0 means neither left nor right subtree is visited till now.If statusValue = 1 , THat means left subtree is visited. If statusValue = 2, means both left and right subtree are visited and now we will add this node->val in the vector the Code is: /** * 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) { if(root == NULL) return {}; stack stk; vector postorder; stk.push({root,0}); while(!stk.empty()) { int status = stk.top().second; TreeNode* curr = stk.top().first; if(status == 2 || (curr->left == NULL && curr->right == NULL)) { postorder.push_back(curr->val); stk.pop(); } else if(status == 1) { stk.top().second++; if(curr->right != NULL) stk.push({curr->right,0}); } else if(status == 0) { stk.top().second++; if(curr->left != NULL) stk.push({curr->left,0}); } } return postorder; } };

[@_neha_43]

i could understand this better than what he explained it in the video for some reason, thankyou!!

[@closer9689]

@@_neha_43 Glad to know😁

[@muskankalra2516]

I did a dry run on 3 different examples, it is very clear now :-)

[@itz_me_imraan02]

Watch it 2-3 times it will be clear 👍

[@himanshusharma261]

+1

[@devanshuvashishtha6932]

My Logic based on Pre-Order traversal Pre-order traversal is root-left-right, and post order is left-right-root. Modify the code for pre-order to make it root-right-left, and then reverse the output so that we can get left-right-root . Create an empty stack, Push root node to the stack. Do following while stack is not empty. 1. pop an item from the stack and print it. 2. push the left child of popped item to stack. 3. push the right child of popped item to stack. reverse the ouput.

[@rabindrapatra7151]

you are remembering code or algo. it is not understanding i feel

[@HemanthaKumarYadav]

If you find the above algorithm tricky like me, you can follow this which is easy and intuitive to understand: A variation of the two stack approach, but uses Collections.reverse() method instead of using a stack. public List postorderTraversal(TreeNode root) { List result = new ArrayList(); if (root == null) return result; Stack stack = new Stack(); stack.push(root); // The idea is to do (root -> right -> left) and then reverse // to get (left -> right -> root) while (!stack.isEmpty()) { TreeNode current = stack.pop(); result.add(current.val); // Push left first so that it's processed after right if (current.left != null) { stack.push(current.left); } if (current.right != null) { stack.push(current.right); } } // Reverse the result to get postorder Collections.reverse(result); return result; }

[@AbhishekThakur-vr4zy]

Hii bhai , your videos are amazing , also in this question no need to use this complex code , it can simply be done like preorder vector postorderTraversal(TreeNode* root) { vector postorder; if(root==NULL) return postorder; stack st; st.push(root); while(!st.empty()) { root=st.top(); st.pop(); postorder.push_back(root->val); if(root->left!=NULL) st.push(root->left); if(root->right!=NULL) st.push(root->right); } reverse(postorder.begin(), postorder.end()); return postorder; }

[@niteshshandilya4226]

thnx bro

[@divyareddy7622]

thank you 🎉

[@sayantangupta6211]

One easy approach can be : Take 1 stack and 1 vector. Initially push root in stack. Then , while stack is not empty, push back the top in vector, pop the top from stack and then push left child 1st and then right child. Finally after stack is empty, reverse the vector. Final postorder traversal will be in the vector //Code: vector postorderTraversal(TreeNode* root) { vectorans; if(root == NULL) return ans; stacks; s.push(root); while(!s.empty()) { TreeNode *p = s.top(); ans.push_back(p->val); s.pop(); if(p->left) s.push(p->left); if(p->right) s.push(p->right); } reverse(ans.begin(), ans.end()); return ans; }

[@PrinceKumar-el7ob]

isn't it what we have done earlier using two stacks !!

[@sunilgrover4178]

In that case, you will be implementing stack functionality using vectors. It means, overall, you will be using stack.

[@shashankojha3452]

Yup. I also came up with this solution. This could have worked as as replacement for single stack method if that extra reverse step at last was not there. Because the space complexity would be O(n) only if we use 1 stack and 1 vector (because we don't generally consider the space used in returning the answer). But since we are reversing the vector in the end , it will add to our time complexity.

[@krishnarajs929]

@@shashankojha3452time complexity will be O(N)+O(N) but in general , the time complexity is O(N) only

[@matrixtoogood5601]

This will be slightly slower than 2 stacks because dynamic array requires doubling of space at times (so insertion can be O(N) in worst case at times) whereas stack is a linked list so insertion is always O(1). Although, in average case both are same

[@akhilesh59]

This was a bit complex, and I had to watch this thrice to understand the concept. It'll be easy to understand if we try to implement the logic on paper. Thank you bhaiya for the explanation!

[@takeUforward]

Yes i have written on pinned comment, that self doing will make this question clear..

[@pulkitjain5159]

@@takeUforward that's what i understood , STACK :-> represent those guys or nodes whose left traversal is totaly complete TEMP: -> remove temp , and replace it with two variables instead 1.) isRightViisted , 2.) nodeThatCompletedTraversal ( both left and right ). vector postOrder(Node* root) { if(root==nullptr) return {}; vector postOrder; stack leftExploredGuys; // stack will only store those guys whose left side is explored Node * node = root; while(node!=nullptr or !leftExploredGuys.empty()){ if(node!=nullptr){ // means this node's left is not explored leftExploredGuys.push(node); // explore left node = node->left; }else{ // if node == nullptr , means left is totaly explored // let's see if the right is explored or not bool isRightExplored = (leftExploredGuys.top()->right == nullptr); if(isRightExplored){ // means this node's overall traversal is over , means this node is of no use Node * nodeThatCompletedTraversal = leftExploredGuys.top(); leftExploredGuys.pop(); postOrder.push_back(nodeThatCompletedTraversal->data); // now stack might contains more nodes whose traversal is completed while(!leftExploredGuys.empty() and leftExploredGuys.top()->right == nodeThatCompletedTraversal){ // if a node's right is a guy who is completly traversed // and it was present in a stack whose left is completly explore // means this node's traversal is also completed nodeThatCompletedTraversal = leftExploredGuys.top(); leftExploredGuys.pop(); postOrder.push_back(nodeThatCompletedTraversal->data); } }else{ // explore the right guy node = leftExploredGuys.top()->right; } } } return postOrder; }

[@manavbansal3953]

@@pulkitjain5159 very good explanation. The dry run was difficult to understand, you explained the reason for every line of code. Thank you.

[@manavbansal3953]

@@pulkitjain5159 could you please explain the other iterative methods of traversal in a similar way please

[@shubhamkumarsingh8818]

this is the more easier appraoch vector postorderTraversal(TreeNode* root) { vector ans; stack st; if(root == NULL) { return ans; } st.push(root); while(!st.empty()) { TreeNode* node = st.top(); st.pop(); ans.insert(ans.begin(), node->val); if(node->left) { st.push(node->left); } if(node->right) { st.push(node->right); } } return ans; }

[@codewithme05]

but this takes time complexity of O(n^2) instead you can just push_back into the ans array and later can reverse it. This reduces to O(n). But it's definetly a good thought

[@lifehustlers164]

Completed 13/54(24% done) !!!

[@sauravchandra10]

Even though I have tried hard, I can't wrap my head around this algorithm. I dont want to memorise this and so I think I am going to skip it. A better approach would be to make slight modifications in the previous approach and instead of using a second stack, I can store the answer in a vector and reverse it before returning it.

[@thomasgeorge4578]

This video is just 🔥🔥, Your dry run is all that was required !!! Amazing!!!

[@staywithmeforever]

didnt understand a single bit didnt explain why that code works even thought u liked it?

[@rabindrapatra7151]

@@staywithmeforever he explained on the start , left, right then again keep going left, in between maintain in stack

[@mahmudaliza4079]

After watching this video, I felt like there is hope in life :)

[@adityapandey23]

Understood Did some dry runs and it was easy and intuitive

[@willturner3440]

This 12 min video took 2 hrs to understand, 😁

[@BRSanush]

Same here

[@rabindrapatra7151]

@@BRSanush because video is focussed on code

[@abhishekjhanji3014]

Another 1 stack approach for this problem vector postorderTraversal(TreeNode* root) { vectorv; if(root==NULL) return v; stack st; st.push(root); while(!st.empty()){ TreeNode*node=st.top(); st.pop(); v.push_back(node->val); if(node->left!=NULL) st.push(node->left); if(node->right!=NULL) st.push(node->right); } reverse(v.begin(),v.end()); return v; }

[@stith_pragya]

Thank You So Much for this wonderful video......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@gourabmukherjee4848]

Very Good Explanation!! I've followed another approach to solve using 1 stack only, the code is mentioned below Stackstack=new Stack(); LinkedListans=new LinkedList(); if(root!=null){ stack.push(root); while(!stack.isEmpty()){ TreeNode ptr=stack.pop(); if(ptr.left!=null) stack.push(ptr.left); if(ptr.right!=null) stack.push(ptr.right); ans.addFirst(ptr.val); } } return ans;

[@gautamjangir8927]

The BEST explanation in the entire youtube....Thanks

[@rishabhkumar8115]

Forget about the source codes, these dry runs are so amazing that they have made life so easy for me

[@piyushacharya7696]

reach++. If you're having trouble understanding it, go back to the previous video and instead of using another stack, just reverse the array. It makes no sense to waste a few hours. The complexity of space and time remains unchanged, and it is also more intuitive.

[@harshitsen5479]

This can be done as preorder as well, just make sure the we are using LinkedList as an implementing class for List, and instead of doing "add" operation, perform "addFirst" operation. while(!mainStack.isEmpty()) { TreeNode temp = mainStack.pop(); res.addFirst(temp.val); if(temp.left != null) mainStack.push(temp.left); if(temp.right != null) mainStack.push(temp.right); }

[@aravintht.k9276]

We can actually use single stack and write similar code like preorder with a simple tweak over it. just traverse left and right instead of right and left. We need to reverse the list at the end. public List postorderTraversal(TreeNode root) { List result = new ArrayList(); Stack stack = new Stack(); if(root == null) return result; stack.push(root); while(!stack.isEmpty()){ root = stack.pop(); result.add(root.val); if(root.left != null) stack.push(root.left); if(root.right != null) stack.push(root.right); } Collections.reverse(result); return result; }

[@pragatiagrawal201]

Finally, after seeing this video my brain is at peace!! Thanks a lot for this😌😌

[@lonewolf-_-8634]

The moment you understand the feasibility provided by Recursion ^-^...

[@kumarsundaram6762]

LeetCode solution using 1 stack and a map (visited array ):- class Solution { public: vector postorderTraversal(TreeNode* root) { if(root==NULL) return {}; stack stk; stk.push(root); map vis; vector ans; while(stk.size()>0) { TreeNode* node=stk.top(); stk.pop(); if(vis[node]==0) { vis[node]=1; stk.push(node); if(node->right) stk.push(node->right); if(node->left) stk.push(node->left); } else { ans.push_back(node->val); } } return ans; } };

[@pulkitjain5159]

you used a graph's dfs approach , treated a tree as a graph , but it tooked some what O(N) exptra space , nice brute force approach

[@nileshsinha7869]

Great explanation man. The dry run really helped to understand. Keep up the good work❤🙌

[@prabhakaran5542]

Understood ❤❤❤

[@theSeniorSDE]

Finally understood this problem well and took notes.

[@amborishnath7755]

can you write down the steps here?

[@pulkitjain5159]

@@amborishnath7755 0 seconds ago THOSE GUYS WHO DID'NT UNDERSTAND , THE DRY RUN , HERE IS SOMETHING TO HELP YOU :) STACK :-> represent those guys or nodes whose left traversal is totaly complete TEMP: -> remove temp , and replace it with two variables instead 1.) isRightViisted , 2.) nodeThatCompletedTraversal ( both left and right ). JUST THIS CODE WITH COMMENTS , YOU WILL UNDERSTAND. vector postOrder(Node* root) { if(root==nullptr) return {}; vector postOrder; stack leftExploredGuys; // stack will only store those guys whose left side is explored Node * node = root; while(node!=nullptr or !leftExploredGuys.empty()){ if(node!=nullptr){ // means this node's left is not explored leftExploredGuys.push(node); // explore left node = node->left; }else{ // if node == nullptr , means left is totaly explored // let's see if the right is explored or not bool isRightExplored = (leftExploredGuys.top()->right == nullptr); if(isRightExplored){ // means this node's overall traversal is over , means this node is of no use Node * nodeThatCompletedTraversal = leftExploredGuys.top(); leftExploredGuys.pop(); postOrder.push_back(nodeThatCompletedTraversal->data); // now stack might contains more nodes whose traversal is completed while(!leftExploredGuys.empty() and leftExploredGuys.top()->right == nodeThatCompletedTraversal){ // if a node's right is a guy who is completly traversed // and it was present in a stack whose left is completly explore // means this node's traversal is also completed nodeThatCompletedTraversal = leftExploredGuys.top(); leftExploredGuys.pop(); postOrder.push_back(nodeThatCompletedTraversal->data); } }else{ // explore the right guy node = leftExploredGuys.top()->right; } } } return postOrder; } JINKO POSTORDER ITERATIVE SAMAJH NAHI AYA EK BAAR READ KARLENA CODE

[@divycodes]

@@pulkitjain5159 ty, this helped

[@indranilthakur3605]

Java solution with one stack - public List postorderTraversal(TreeNode root) { List res = new ArrayList(); if(root == null) return res; Stack s = new Stack(); s.push(root); while(!s.isEmpty()){ root = s.pop(); res.add(0, root.val); if(root.left != null) s.push(root.left); if(root.right != null) s.push(root.right); } return res; }

[@nawabkhan4916]

great work, and have lots of sponsor ad so that you can provide great videos.

[@coding8000]

Again @takeUforwad, just letting you know, again that's stuff you have done, is GOD's own work, thank you for from bottom of my heart, thanks !!!

[@starr_lord0]

Just a small changes in your previous code(inpired from you). vector postOrder(Node* root) { // Your code here vector res; stack st1; st1.push(root); while(!st1.empty()){ root=st1.top(); st1.pop(); res.push_back(root->data); if(root->left!=NULL) st1.push(root->left); if(root->right!=NULL) st1.push(root->right); } reverse(res.begin(),res.end()); return res; } Simple!!!

[@cinime]

Understood! So awesome explanation as always, thank you very much!!

[@abhaykumarsingh3266]

Don't go with striver's appoarch(its is very tricky) just use 1 stack with previous video approach List ans=new ArrayList(); if(root==null){ return ans; } Stack st1=new Stack(); st1.push(root); while(!st1.isEmpty()){ TreeNode temp=st1.pop(); ans.add(0,temp.val); if(temp.left != null){ st1.push(temp.left); } if(temp.right != null){ st1.push(temp.right); } }

[@imKushGupta]

ans.add(0, temp.val); operation across all nodes becomes O(N^2) in total. The operation ans.add(0, temp.val); takes O(N) time for each insertion because it requires shifting elements to the right.

[@imKushGupta]

This is right code bro..... TC- O(2N) SC- O(N) List ans = new ArrayList(); if (root == null) { return ans; } Stack st1 = new Stack(); st1.push(root); while (!st1.isEmpty()) { TreeNode temp = st1.pop(); ans.add(temp.val); // Add to the end of the list if (temp.right != null) { st1.push(temp.right); } if (temp.left != null) { st1.push(temp.left); } } // Reverse the list at the end Collections.reverse(ans); return ans;

[@rabindrapatra7151]

video starts at 0:42

[@arunachalamm3399]

Amazing series bhai, from 1:28 in 1.5 x was funny lol😂😂

[@anandtripathi]

Here is simpler code using logic of iterative preorder. vector postorderTraversal(TreeNode* root) { vector ans; if(root==NULL) return ans; stack st; st.push(root); while(!st.empty()) { auto node = st.top(); st.pop(); ans.push_back(node->val); if(node->left) st.push(node->left); if(node->right) st.push(node->right); } reverse(ans.begin(),ans.end()); return ans; }

[@samuelfrank1369]

UNDERSTOOD. THANKS A LOT.

[@shivangisrivastava1158]

Finally after 1-2 dry runs, clearly understood. This one is really bit complex.

[@SHASHANKRUSTAGII]

indeed

[@maazulhaque7293]

Great Explanation, such a tough topic and how easily you explained... Hats of you man

[@amandeep0148]

Bhaiya you really taking us forward. Thank you.

[@ruchighodasara1644]

Dry run is very helpful.

[@baibhavsingh9225]

i have done it this way. its a bit simpler i think vector ans; stack st; st.push(root); if(root==NULL){return ans;} while(!st.empty()) { TreeNode* cur=st.top();ans.push_back(cur->val);st.pop(); if(cur->left!=NULL){st.push(cur->left);} if(cur->right!=NULL){st.push(cur->right);} } reverse(ans.begin(),ans.end()); return ans;

[@shrishtikumari4324]

Yeah. Much easier solution. Thanks a lot!!!

[@Rajesh-op8zx]

Space complexity will be O(H) and H here is the height of tree , stack can have at max H elements only at one time so S.C is not O(N) here .

[@harshitsangwan890]

Yes, you are correct.

[@jasonbrody4618]

Liked. Cfbr will watch after some time

[@trashcan-md7cw]

The intuition of this problem is not understandable in 1 watch. But rewatching it and testing on some trees will make it clear... But yeah this is tough...

[@amitsinghrana6619]

Had to brain-storm for *6 hours* before understanding the part { while(!st.empty() || st.top()->right) } It's basically checking if this node was right child of some other node, if it was then we have visited both childs of that node, so print it and remove it from stack. *temp* stores right child when going down the tree, and contains recently printed node when going up the tree.

[@huungryyyy]

when i saw the questions i did the 2 stack approach of the previous video but instead of taking 2nd stack directly store the answer into result vector and and just reverse the result vector.

[@ManishKumar-ml8wz]

But for reversing you end up taking O(n) extra time

[@vakhariyajay2224]

Thank you very much. You are a genius.

[@bhagyasingh3076]

Just do a reverse preOrder and reverse the final vector vector postorderTraversal(TreeNode* root) { vectorpostOrder; if(!root)return postOrder; TreeNode *node = root; stackst; st.push(node); while(!st.empty()) { node = st.top(); st.pop(); postOrder.push_back(node->val); if(node->left)st.push(node->left); if(node->right)st.push(node->right); } reverse(postOrder.begin(),postOrder.end()); return postOrder; }

[@bharathkumar5870]

it is not reverse pre order..it is root---right--left order

[@SHASHANKRUSTAGII]

wow man, and yes bharat is right

[@SK-cm1hn]

Then the Solution is in O(N Log N) , this solution is in O(N).

[@VAISHNAVIP-z6j]

Superb sir❤

[@mriduljain1981]

completed lecture 12 of Tree playlist with some difficulty and by watching it twice and dry running it on own xD..

[@UECAshutoshKumar]

Thank you sir

[@areebahmadsiddiqui2648]

I want DP series as well

[@vipulchoudhary2419]

This is also using 1 stack. // TC --> O(N)[Tree traversal] + O(N)[Reversing the array] // SC --> O(N) class Tree { //Function to return a list containing the postorder traversal of the tree. ArrayList postOrder(Node root) { ArrayList postOrder = new ArrayList(); if(root == null) return postOrder; Stack st1 = new Stack(); st1.push(root); while(!st1.isEmpty()) { Node node = st1.pop(); postOrder.add(node.data); if(node.left != null) st1.push(node.left); if(node.right != null) st1.push(node.right); } Collections.reverse(postOrder); // TC --> O(N) return postOrder; } }

[@adityaaditya7286]

We use second stack basically to reverse the result which u are doing by reversing the array. These are same things. What if i say you to don't store anything and print directly?

[@rajeshbora2013]

Great explanation bro 👏👏👏

[@theSeniorSDE]

Lots of curr and push & push curr in this problem 😂 definitely i will have to watch it once again to understand the algorithm better.

[@takeUforward]

Yeah, its slightly tricky, i will highly recommend to do it by yourself on pen and paper.. to understand it better.

[@theSeniorSDE]

@@takeUforward Took a break for 2 day and revised all the previous topics that i learnt from the previous videos. Now starting again from where I left. 😎

[@Kpriyasing]

Amazing content!!

[@parthsalat]

Understood!

[@Yash_Parashar]

In first condition there should be AND not OR , if I am wrong correct me.

[@rohandeshmukh3989]

Yeah actually that why it is going in the else part where curr is not null otherwise how will it go in that section

[@project_eth]

understood, day 3

[@DeadPoolx1712]

UNDERSTOOD;

[@SHASHANKRUSTAGII]

If we know Iterative post order with 2 stacks, is it required to do with one stack? I mean the time complexity is still same? still the interviewer can ask na? do with one stack?

[@_hulk748]

Understood sir❤🙇‍♂🙏

[@divyaagarwal3091]

Thankyou so much sir!

[@Learnprogramming-q7f]

Thank you Bhaiya

[@studynewthings1727]

Understood.

[@as_a_tester]

tysm striver bhai

[@divyaagarwal3091]

Understood!

[@JohnWick-kh7ow]

Your videos are amazing. Just one suggestion: You could have given this more time. We would understand it better.

[@Joy-x9m]

For this video, it was difficult for me to follow the small red dot. I bit more visible would have been nice.

[@creativeprojects217]

thank you sir♥

[@eklavyaprasad5009]

Thanks bhaiya

[@heavenlyway5824]

Hi Raj, I really like all your videos. However missing point is can tell me some 2 minutes, how you come to particular logic, what are your thought process and intuition beyond approach. it will be extremely helpful. For example: in previous video, you said take 2 stacks , 1st insert root to stack1, then take top element of stack1 to stack2, then find left and right of top of top element in stack2, then repeat the same to get the answer. -> I want to know how you come up with this logic? can you take 2 minutes to explain your thought process in this.

[@sachinpathak3084]

there are few questions which required intuition and few question which needs to memorisation

[@shreyshah4220]

No

[@RahulKumar-rk1tf]

Start- 00:40

[@Dineshsharma-ec6ys]

I have problem. I just watch your video understand the approach and able to code and solve the problem .but after a week i find myself not unable to solve the same problem . so I have to go through the video again.

[@sauravpandey3802]

did you find any solution ??

[@lakshsinghania]

obvio. revision is must studying for one time doesnt make u remember all the things

[@krishnavamsichinnapareddy]

Understood 👍

[@ordinaryhomosapien1181]

This explanation is great 👍

[@manaslahon1031]

if 6 has already been removed from the stack how is it accessible to compare with the st.top()->right? Timestamp- 6:42