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

0:00 - Read the problem
0:40 - Drawing Explanation
10:00 - Coding Explanation

leetcode 145

#neetcode #leetcode #python

[ben]

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

[rdwok]

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

[swapnadeepmukherjee]

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

[neelmajm]

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

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

[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

[acecool]

O_O, can't believe this really works O_O_O_O

[SahinSarkar-grvm]

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.

[atatekeli]

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

[sangwookim]

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

[lalitvinde]

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]

[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;
}