Binary Tree Postorder Traversal (Iterative) - Leetcode 145 - Python

[@priteshranoliya1969]

ok! this is hard to understand..

[@ben1553]

Better solution for iterative is to reverse the solution you get from doing the reverse preorder traversal, no need for extra array.

[@niranjanapn9641]

How did you come up with that? Could you please explain?

[@davidteklea1032]

No, you would have the left and right messed up

[@yuwensun1006]

@@davidteklea1032 you can modify the pre-order case by changing left and right, then reversing its output will give you the answer for post-order traversal.

[@himage6540]

​@@yuwensun1006true

[@rdwok14]

The iterative solution has got to be at least a medium.

[@birdbeakbeardneck3617]

Yep harder than it looks

[@80rian-jeong]

isn't this just like preorder traversal but left and right order switched and append to the result in reverse? below is the solution with very small modification from neetcode's preorder traversal class Solution: def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]: res = [] stack = [] cur = root while cur or stack: if cur: res = [cur.val] + res stack.append(cur.left) cur = cur.right else: cur = stack.pop() return res

[@neelmajm5868]

I think it is better to create a tuple (node, False) instead of having two lists.

[@antimuggle_ridhi2565]

same complexity still

[@patrickfeeney4180]

Nice. Very simple.

[@haoyuguo3929]

using two stack is amazing.

[@acecool1715]

O_O, can't believe this really works O_O_O_O

[@shanthureddy4234]

thanks for the explantion

[@49-farhaanali86]

Lots of love man......!

[@vivekmit06]

Thank you very much!!!

[@SahinSarkar-gr6vm]

This soln doesn't have stack space complexity as height of tree, at least this specific implementation. I tried it with a tree of height 3, but I got height 7.

[@dantedt3931]

Thanks dude

[@yynnooot]

I'm curious why you went with this approach as opposed to solutions that reverse the final result, or add to the front of the result list (instead of pushing to back)? Is that too 'hacky'? I feel like I'd start confusing myself during an interview while coming up with a solution like yours. It's very different than your Preorder Traversal approach

[@GorgeousPuree]

Yes, because it is hacky. Essentially when you reverse the final result, you just get the right answer, but you don't really do the postorder traversal. Interviewer may not accept your code if you just reverse preorder traversal. Also here's a better explanation on why hacky solutions are not good: "Again, as I commented at in the most popular answer, strictly speaking, this solution for the post order is incorrect. Even though the final result is correct, imagine if there are topological dependencies among the nodes, the visiting order would be significant. Simply reversing the preorder result isn't right."

[@tjalferes]

I like this solution, but I also like another solution: function postOrder(root) { if (!root) return []; const res = []; const S = [root]; while (S.length) { const i = S.pop(); res.unshift(i.data); if (i.left) S.push(i.left); if (i.right) S.push(i.right); } return res; }

[@Kai-wi1md]

Then you come up with the cost of the unshift() function which is O(m) - m is the length of the tree.

[@atatekeli9295]

What if we said stack.append(cur.right, cur.left) instead of stack.append(cur.right) and stack.append(cur.left) separately?

Would you say that to set left and right pointers to null along the way is WRONG? Cause that makes it trivial

[@swapnadeepmukherjee007]

@NeetCodeIO: The code is not fully visible on the screen and also hard to understand. Please fix the same.

[@AustinWeeks]

my friend be grateful that he even makes these videos the last line just says : vist.append(False)

[@sangwookim5551]

Hi I appreciate all of your videos. They have been immensely helpful. But one thing that I am dissatisfied is how many ads you put on your videos. There are many times after finishing 2 ads, another 2 ads run. Please help to fix this

[@Sharmav03]

use brave bro or maybe an extension for yt ad block

[@lalitvinde1441]

hello I get this solution but don't know the intuition for doing so if anyone can help me out def postorderTraversal(self, root): if not root: return [] stack = [root] result = [] while stack: current = stack.pop() result.append(current.val) if current.left: stack.append(current.left) if current.right: stack.append(current.right) return result[::-1]

[@chrischika7026]

you are doing reverse preorder