L11. Iterative Postorder Traversal using 2 Stack | C++ | Java | Binary Tree

Entire DSA Course: takeuforward.o...
Check our Website:
Linkedin/Instagram/Telegram: linktr.ee/take...
#treeSeries #striver #placements

[@takeUforward]

Please likeeee, shareeee and subscribeeeeeeee :) Also follow me at Insta: Striver_79 Please watch it at 0.5x or 0.75x, I mistakenly uploded at 2x 🥺

[@rajasethi2341]

Actually i was watching at 1.75X and suddenly everything changes

[@democratcobra]

Great Explaination...Thanks for uploading....

[@someone-zi8xc]

@@rajasethi2341🤣

[@preetamkumar838]

I watched it whole at 1.5x and realized, later i read the comments 😂😂

[@ARUN-ik2nb]

@@rajasethi2341 me too🤣

[@codermal]

We can also see it as preorder-> root left right swap left, right -> root right left reverse -> left right root So in first stack we apply pre-order traversal code, and 2 stack is to reverse it, basically we need 2 stack as we can't move from child to parent in tree

[@ashtonronald]

Thanks! Really helpful!!

[@harshitmalhotra8627]

This year's only video I have watched at 0.5x.

[@CosmicWhale7777]

yes haha

[@omkarshendge5438]

same lol

[@shortsmaker0308]

Same 😁

[@theSeniorSDE]

Striver, had to slow down the video speed to understand it better. 😂 Completed this as well. Steps : 1. initial config : Take the root and put it in the 1st stack. 2. Now, take the top from the 1st stack and put it into the 2nd stack 3. After that, if the top in 2nd stack has left → add it in 1st stack. And if the top in 2nd stack has right → add it in the 1st stack. 4. Now again, take the top from the 1st stack and put it into the 2nd stack. Repeat step 2 & 3 untill 1st stack is empty. 5. Pop the element from the 2nd stack and print.

[@takeUforward]

Yeah by mistakenly, i uploded it at 2x 😂

[@aditiranjan303]

Thanks for writing the steps clearly

[@rigaut-valorant6105]

@@takeUforward and I still watched it at 1.5x

[@vishalplayzz2580]

@@rigaut-valorant6105 Lmao

[@ChefnCoder]

u explained it really good, any chances u have made notes of tree series cause i am sure it will be really good

[@JayPanchal03]

Understood the concept first and then wrote the code on my own and later found out that it is exactly same as in the video got confidence....

[@SaurabhSingh-nv9jj]

we can also use the ans vector which we are going to return as the second stack, but in the end we will have to reverse the vector before returning it.

[@namanchhabra4136]

In Stack 1 we make ROOT RIGHT LEFT ( like we did in preorder -> root left right ) Stack2 is used for reverse : - if we reverse the Stack1 it will give Postorder which is LEFT RIGHT ROOT

[@tanishq2766]

I was not at all able to come up with this, I hardly give up on problems, this was impossible for me to think fr!

[@mohit7717]

You can make everyone understand in 2x too .. that's the quality in you.. Great man!

[@26_jamkhandedattatray59]

i shocked when i played this video at 1.75x speed, after read out description I understand what actually happened😂. Anyway but lec is awsome

[@Shourya_performs]

xctly

[@codding32world50]

Same here lmao

[@Lakshya-f4l]

😂😂

[@valiz2628]

explanation is so beautiful , so elegant , just looking like a wow

[@devanshmesson2777]

Those who are unable to understand the intuition behind this, Watch the next video which uses 1 stack, That video is relatively intuitive.

[@stith_pragya]

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

[@605_samikrdas4]

in c++ code: vector inOrder(Node* root) { vector ino; stack s; Node* p =root; while(true) { if(p!=NULL) { s.push(p); p=p->left; } else { if(s.empty()==true) break; p=s.top(); s.pop(); ino.push_back(p->data); p=p->right; } } return ino; }

[@DevanshuAugusty]

what is the intution behind this solution...you are directly junmping to the solution

[@letsrock7354]

Rather than taking a stack we can save that in the resultant vector and then reverse it in the end We can save some space

[@iamsalonitayal]

I was already watching ur vids at 1.5x . But here:-) for a moment I thought my mind was processing the content slowly. lol. Anyways awesome lectures.

[@lifehustlers164]

Completed 12/54(22% done) !!!

[@nandkishor999]

hello sir this series is really great. I tried many series on the youtube but your's one is best thank you so much.

[@K_EN_VisheshSaini]

We can just use the preorder traversal code and reverse the insertion of left and right nodes in the stack and also the array in the end before returning it. Code:- class Solution { public: vector postorderTraversal(TreeNode* root) { vector ans; if(root == NULL) return ans; stack st; st.push(root); while(!st.empty()){ TreeNode *temp = st.top(); st.pop(); ans.push_back(temp->val); if(temp->left!=NULL) st.push(temp->left); if(temp->right!=NULL) st.push(temp->right); } reverse(ans.begin(), ans.end()); return ans; } };

[@bambu-mq9zg]

we can also use queue and stack for it... like root >right>left then store it into queue from left class Solution: # Return a list containing the inorder traversal of the given tree def postOrder(self,node): s=[node] l=1 ans=deque() while l!=0: a=s.pop() l-=1 ans.appendleft(a.data) if a.left!=None: s+=[a.left] l+=1 if a.right!=None: s+=[a.right] l+=1 ans=list(ans) return ans

[@Rebantaprat]

Striver what is the intuition for using 2 stack 🤔?

[@tonyconor681]

I puted as usual 2x then suddenly I feel it's like 3x , then I did 1.25 final calmly understood his words holy moly

[@pranjal1100]

Was watching the playlist at 1.35x when I came across this XD

[@AnkurSingh-cv1ls]

We actually don't require second stack.....as shown here: vector postorderTraversal(TreeNode* root) { if(root==NULL) return {}; stack st1; vector ans; st1.push(root); while(!st1.empty()){ TreeNode* temp=st1.top(); st1.pop(); if(temp->left!=NULL) st1.push(temp->left); if(temp->right!=NULL) st1.push(temp->right); ans.push_back(temp->val); } reverse(ans.begin(),ans.end()); return ans; }

[@ManyaNayak-md7xr]

it will give tle

[@viveksingh_01]

@@ManyaNayak-md7xr it will not

[@prabhakaran5542]

Understood ❤

[@neelgorasiya7199]

I used to watch your videos 1.5x. But when I did it in this video Ahhhh!! NFS rocks........

[@nihalshukla7718]

I was refreshing again refreshing then open in new tab.. after that I came to comment section.. then I realize my pc is working fine.

[@bhavkushwaha]

Thankyou Striver, Understood!

[@andersonbhat6885]

Striver bhaiya as a first timer looking at this algo i'm not sure whether we should be able to think of such an algo on our own ,cause i couldn't think of it or are we expected to get this after some practice ?

[@takeUforward]

There are certain things you have to know in order to do.

[@justarandomguy6106]

@@takeUforward means we have to remedy these types of solution like algorithm

[@samuelfrank1369]

UNDERSTOOD. THANKS A LOT.

[@raj-nq8ke]

begins at 0:44

[@arnabdutta4662]

if stack 2 is made integer dayatype then space requirement would be reduced :)

[@raviketan2957]

Thanks for whatever u r doing.

[@5076_GidijalaDineshSurya]

Loved the lecture striver! I have a doubt, Why not just use a vector instead of 2nd stack and then reverse it? Why did we use 2 stacks?

[@piyushmahale9024]

This is the first video that i have seen at normal speed 😂

[@ritamkabiraj8035]

st2.push(node) instead st2.add(node) [Time 3:09]

[@liteni368]

Striver bhaia tussi great ho

[@AnkitOli-d2g]

Can we directly add the elements to output arrayList and print it in reverse order,without using st2. Will it make space complexity a bit efficient?

[@rupalikumari8829]

Understood : )

[@mriduljain1981]

completed lecture 11 of Tree playlist.

[@alienx2367]

Why did you suddenly tuned into Eminem

[@ishankbansal9239]

😂🤣

[@shubamgoswami]

EMINEM IS RAP GOD AND STRIVER IS INTIUATION GOD

[@nawabkhan4916]

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

[@mannmehta4841]

Easier approach with only one stack without infinite loop, but yes O(N) extra space - Code: void inordere_traversal_interative(Node* root) { stack st; st.push(root); unordered_map vis; while(!st.empty()) { Node* node = st.top(); if (node->left != NULL and !vis[node->left]) { st.push(node->left); continue; } if (node->right != NULL and !vis[node->right]) { st.push(node->right); continue; } cout

[@parthh1112]

void inorder(TreeNode *&root) { stack s1, s2; s1.push(root); while (s1.size() > 0) { TreeNode *x = s1.top(); s2.push(x); s1.pop(); if (x->left) s1.push(x->left); if (x->right) s1.push(x->right); } while (s2.size() > 0) { cout val

[@debangshubanerjee1311]

What is the intuition behind using 2 stacks?

[@subhajitdey135]

In Preorder and inorder we were going from parent to child but as you can see in postorder we need to keep the track of parent before moving to the right child. So to keep the track we are using two stacks.

[@UECAshutoshKumar]

Thank you sir

[@t-anime517]

Understood😊

[@rishidubey5037]

Great Content.

[@jasonbrody4618]

Liked. Cfbr will watch after some time

[@apmotivationakashparmar722]

Thank you so much.

[@ARUN-ik2nb]

Short and sweet 👌

[@rishabhshairy972]

We can use One Stack and One List List can be used to store values and return public List postorderTraversal(TreeNode root) { List postOrderList = new ArrayList(); if (root == null) { return postOrderList; } Stack opStack = new Stack(); opStack.push(root); while (!opStack.isEmpty()) { root = opStack.pop(); if (root.left != null) { opStack.push(root.left); } if (root.right != null) { opStack.push(root.right); } postOrderList.add(root.data); } Collections.reverse(postOrderList); return postOrderList; }

[@smitdumore1064]

Making the video duration short by speeding it up is a genius strategy to get more clicks,

[@snehilsinha5624]

Why don't we store the postorder traversal in the final output vector itself and reverse it at the last rather than using an extra stack for reversal ?

[@vakhariyajay2224]

Thank you very much. You are a genius.

[@akashverma5756]

what is intuition behind this solution? I think this solution is inspired from from the fact that post order traversal is opposite of reverse preorder traversal. (left - right - node) == !(node - right - left)

[@DeadPoolx1712]

UNDERSTOOD;

[@lourduradjou182]

super hero striver

[@anshikagupta5858]

Thankyou Striver:)

[@rishabmalhotra6980]

at 0.5 speed it seems like striver is begging in last LOL

[@yashgupta-fk3zc]

aree bhaaiyaa bhaiyaa halke halkee... SLE(SPEED LIMIT EXEDDED) ajaygi barna:xd

[@eduflex7931]

Too good🤣🤣🤣

[@curs3m4rk]

AWESOMMEE !!! LOVED IT

[@Learnprogramming-q7f]

Thank you Bhaiya

[@om-prakash-yadav]

mujhe laga mera dimag kaam nhi kar paa raha ..fir dekha ..video thoda jyada hi speed hai 😂😂😂😂😂😂😂😂

[@fantasyillusion]

for the python code # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]: postorder = [] if root==None: return postorder st1,st2=[root],[] while st1: root = st1.pop() st2.append(root) if root.left: st1.append(root.left) if root.right: st1.append(root.right) while st2: postorder.append(st2.pop().val) return postorder

[@subhamsingh9553]

Bro if you return st2[::-1] instead of postorder array(you don't need a third list) you will get the answer second while loop is not necessary

[@atharvacodes3705]

The space complexity should be O(N) right? Even though we're using two stacks, in the end, sum of number of nodes in both the stacks is N, where N in the number of nodes in the tree.

[@lakshay6994]

yes

[@codding32world50]

yess

[@lavanyaprakashjampana933]

we love your content and we love you....🖤

[@coolgaurav5163]

Understood

[@ashitasrivastava681]

UNDERSTOOD!

[@_hulk748]

Understood sir🙏🙇‍♂❤

[@dhivyashri6554]

hello bhaiya! thank you so much for the video, but i think it's sped up could u check that if possible

[@AkashKinage-ir9ez]

Thank you stiver for your amazing playlists :)

[@RahulKumar-rk1tf]

Start at- 00:40

[@as_a_tester]

tysm striver bhai

[@jambajuice07]

ok will have to cram this method

[@runtime379]

awsome series bhaiya

[@surabhichoubey2987]

Bhiya plz use white pan while explaining

[@mohitharpalani6025]

understooood

[@ayushmansingh2650]

please watch it 0.5 of normal speed.

[@prantikofficial]

so true! 😂😂

[@ujjwalsharmaiiitunacse3884]

Danetawasi code :- class Solution{ public: vector postOrder(Node* root) { stack st; stack st1; vector ans; if(root!=NULL) st.push(root); while(!st.empty()) { Node* temp =st.top();st.pop(); if(temp==NULL) { continue; } st1.push(temp->data); Node* left=temp->left; Node* right=temp->right; st.push(left); st.push(right); } while(!st1.empty()) { ans.push_back(st1.top()); st1.pop(); } return ans; } };

[@krishnavamsichinnapareddy]

Understood 👍

[@saumitrakaushal5369]

me watching the whole series at 2x , suddenly this video at 4x :D

[@PrakharKulshrestha-q6e]

understood

[@SURISETTISRIRAMNITAP]

can we use vector in place of second stack as it is just holding the node data, if use the vector we can reverse it at the end!!

[@ak67373]

If we add in list instead of 2nd stack and then reverse it?

[@Student-j4u]

yeah we can

[@deepbytes4854]

# Python code stack1 = [root] # initialise stack with root stack2 = [] while stack1 : node = stack1.pop() # pop from stack1 if node is not None : stack2.append(node.val) # in stack2 append node.val if node.left is not None : stack1.append(node.left) if node.right is not None : stack1.append(node.right) return stack2[::-1] # return stack2 in reverse

[@ornatetrout]

How SC is 2N? At any point of time we are going to store a node only once. The node can be present in stack 1 or in stack 2. So, at max sum of size of stack 1 and stack 2 at any point of time can be N. So, SC should be O(N). Striver bro please clarify my doubt.

[@reshihashim4094]

1kth like is mine ❤️🔥

[@priyaanshusoni]

We can Solve this problem by O(N) also Bhaiya , /** * 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: // void PostOrder(TreeNode* root , vector&ans){ // if(root==nullptr) return ; // PostOrder(root->left,ans); // PostOrder(root->right,ans); // ans.push_back(root->val); // } vector postorderTraversal(TreeNode* root) { // vectorans; // PostOrder(root,ans); // return ans; //post order traversal using one stack stack st; vectorans; if(root==NULL){ return ans; } st.push(root); while(!st.empty()){ TreeNode* temp =st.top(); st.pop(); ans.push_back(temp->val); if(temp->left) st.push(temp->left); if(temp->right) st.push(temp->right); } reverse(ans.begin() , ans.end()); return ans; } }; AND PLEASE PLEASE BRING LATEST TREE & GRAPH SERIES .

[@1tav0]

Thank you so much striver for these series. You are a great help to people like me

[@altamashsabri8142]

Understood

[@shivangisrivastava1158]

Amazing video!

[@rahulsrivastava1040]

U r in final year ?

[@abhaymandal4903]

I think tc will be 0(2n)

[@tusharrustagi5729]

understood

[@lone_wolf7721]

instead of using another stack can't we use vector and reverse it?

[@takeUforward]

Yeah as you wish. Concept stays the same.

[@ayushop1921]

@@takeUforward so bhaiya in this approach the space complexity will be O(1) na ?\

[@shardulwagh904]

@@ayushop1921 In the worst case we add all nodes of the tree to the stack, making it O(n)

[@deepakgurjar3746]

but for this u heave to take care of node and value...in vector u push data but for check whether left of node or right of node exist there must be a node u are checking not data\value :)

[@mixshots1801]

My solution for iterative post-order traversal and it passed all test cases in leetcode: /** * 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) { vector v; auto node=root; stack st; while(true){ if(node!=NULL){ st.push(node); v.push_back(node->val); node=node->right; } else{ if(st.empty())break; auto temp=st.top(); st.pop(); node=temp->left; } } reverse(v.begin(),v.end()); return v; } }; TC=O(N+N)

[@sahilkumarsingh8517]

Understood😁

[@rishabhgupta1222]

Watch it in 0.6x for a normal person

[@utkarshsharma6650]

understoooood. thanks :)