Iterative Postorder Traversal of Binary Tree

[@HimanshuSharma1981]

This guy was my junior in Grad School, and here I am learning Data structures from him. Kudos Tushar!

[@kartikkankurte717]

This is one of the underated channels

[@nikhilsharad9553]

Amazing tutorial and your way of explanation is incredibly easy to follow. Thanks for such wonderful tutorials.

[@dominiquesilva4756]

The method that you used made it very easy for me to understand.

[@kevinmeraz8159]

Amazing. So simple and clear. Huge help. Thanks!

[@satang500]

Wow I really like the idea of using two stacks. Writing correct code using only one stack without mistakes for a short time was quite challenging for me. As you commented I'll be expecting your video for using one stack too. :)

[@vjnvisakh]

Thanks a lot ... had this single stack code ... but it was getting a bit confusing ( specially while printing the last node -- root). This code is much better and much more logical.Thank you once again Tushar

[@xenobob2773]

Love how the Indian guys start out with 'Hello Friends'.

[@sachinrana309]

These videos got me job!!!Thanks a lot

[@punitoza84]

Thanks Tushar, your videos are helping a lot and making the data structures revision far less daunting.

[@aakashbhatia]

easy to understand explanation

[@sudipsaha9677]

thanks ..u made my coding journey easy

[@karthikr644]

Very useful, I was struggling to find an approach. This is a neat solution.

[@AmoghNatu]

Thanks Tushar. This is a great solution. However, can you also explain the thought process of actually "arriving at the idea of using 2 stacks"? I'm struggling with that? Meaning, how did you get the idea in the first place that we can use 2 stacks to solve this? Can you also put here the thought process of arriving at this solution approach? Many thanks!

[@albertt9097]

you can think of the 2nd stack as a visited tag (another approach to solving this). Or you can think of it as a 2nd push to the stack (a 3rd approach similiar to his other postorder vid)) Lastly you can see it as a reverse preorder visualized here.

[@rituagrawal2218]

Very nice video. Waiting for 1 stack postorder iterative traversal video . :-)

[@koustavchatterjee2907]

Java Single Stack Solution code.geeksforgeeks.org/n1XgVe

[@rituagrawal2218]

Thanks Koustav

[@cantwaittowatch]

Very nice tutorial Tushar. I tried using one single stack which needed a counter to keep track of how many times elements have been popped or visited so not to process them again. Gets bit tricky!!!

[@fxjing]

very good approach and explanation. thanks.

[@muskanroxx22]

The method for using two stacks doesn't seem very intuitive, to me all the iterative codes for Preorder, Inorder, and Postorder don't seem intuitive enough. I am able to understand this but if someone would have asked me to directly come up with an iterative algorithm for traversals it wouldn't strike me. So, do we just learn this as an algorithm- it is what it is? I understand why it works looking at it's implementation, are we supposed to cram some of these things in order to prepare for our interviews?

[@savantdude]

let me guess.. you have trouble understanding the fundamentals of CS too?

[@jeffereycountryman6771]

very clear. Thank you very much.

[@sidk5919]

thanks gautam gambhir

[@tusharroy2525]

lol

[@OverLordOfDa3rdWorld]

Wow, amazing. Thank you so much!

[@Null_pointer_exceptn]

Thanks. we can also use just 1 stack .

[@kshawal]

Thanks.. very easy to understand

[@rishabh7011]

Thank you sir ji

[@FamousEgyptboy]

very well explained Thank you !

[@shwetashukla7291]

Thanks this was very helpful

[@talaviss123]

very well explained

[@engel15496]

Nice video!

[@naveennagar09]

thank you sir..very well explained :)

[@someshsharma1094]

Nice video... Please upload the Postorder Traversal with Single Stack... :)

[@urrahman196]

Great video, please rename it using two stack

[@ninadpradhan6566]

nice one bud!

[@adhishmalviya2408]

Nice

[@trangbui1910]

thank you

[@lohittalasila]

Thank you :)

[@yunus.yildirim]

Can u add a new lesson for Internal Path Reduction trees?

[@raghuram463]

Does Non-recursive algorithm and Iterative algorithm mean the same for Post order traversal of Binary tree?

[@sumeetsood232]

can you please share link where this is done by reccursion, i cannot find it on your channel

[@anuragdani9739]

I have a question, why have you implemented with Deque instead of Stack in the implementation?

[@Kavishkhullar]

this particular solution works but why is that? am i just suppose to memorize this logic/algorithm?

[@apple2092]

Thanks for sharing and it's a good solution. But I'd more like to know how to figure out such a solution?

[@raghavchadha9133]

data structures book Seymour lipschutz ....traversing binary tree using postorder ..

[@bighneshsabat5374]

nice explanation,but i need one stack implementation.

[@GaganGrewalf095]

It will basically be a Depth-First traversal ? We still need some kind of tracking collection to record visited nodes... is that correct ?

[@wentaohu1706]

hi Gagan, I can answer your question, based on your assumption: "We still need some kind of tracking collection to record visited nodes", I wrote 2 algorithms to compare , a wrong one and a correct one, and each has detailed explanation, pls check my github repo: github.com/adalucky1234/Tree-Implementation-Java , go to master branch, then you easily find it. Thanks!

[@shivajunna]

How did you come up with two stacks idea?

[@creativity4416]

GOOD ONE (Y)

[@raghavchadha9133]

there is some method ..right child is negative ...what abt that ..it is not considered here

[@raghavchadha9133]

+Tushar Roy we are pushing right child as negative ..nd left child positive ...then. backtrack if no left child .. then process positive ...if there is negative right child ..then we make it positive nd again process it . .its done In my book ..bt my basic question is why we take right child as negative

[@raghavchadha9133]

+Tushar Roy its done using one stack ...bt I watched ur one stack ..bt there also ..there was no negative right child

[@prabhakarpalanivel6472]

This is more of a "reversed" preorder search followed by reversing the list using another stack

[@SangharshSeth]

can you link to a true iterative implementation

[@manvityagi6529]

The only bad thing is : He rarely shares the thought process and jumps directly into the solution.

[@akshatjain6854]

rightly said

[@savantdude]

ahh right, everything has to be fed to you so you can regurgitate it in interviews!

[@twndomn]

Assuming this is Java, it's Not recommended to use Stack data structure, use Deque instead. Stack was implemented using vector in the early Java days, outdated and inefficient, also bad for job interview.

[@swagatpatra2139]

public List postorderTraversal(TreeNode root) { Deque q = new LinkedList(); List res = new ArrayList(); if(root == null) return res; q.addLast(root); while(!q.isEmpty()){ TreeNode curr = q.removeLast(); res.add(curr.val); if(curr.left!=null) q.addLast(curr.left); if(curr.right!=null) q.addLast(curr.right); } Collections.reverse(res); return res; }

[@Manishkumar-zj9zw]

void postorder(node n) { if(n==null) { return; } Stack s1=new Stack(); Stack s2=new Stack(); s1.push(n); while(!s1.isEmpty()) { n=s1.pop(); s2.push(n); if(n.rchild!=null) { s2.push(n.rchild); } if(n.lchild!=null) { s2.push(n.lchild); } } while(!s2.isEmpty()) { n=s2.pop(); System.out.print(n.data+" "); } } whats wrong with it??

[@raghavchadha9133]

pls reply sir

[@hum2712]

Hindi m padhiye sir please