Problem statement

https://leetcode.com/problems/binary-tree-postorder-traversal/

Solution 1

If we are not allowed to use recursion, we need to use stack. First I invented solution, where we keep number of visited children of node. But actually, there is more elegant solution, where we use only visited flag.

Complexity

Time and space complexity is O(n).

Code

class Solution:
    def postorderTraversal(self, root):
        out, stack = [], [(root, False)]
        while stack:
            node, visited = stack.pop()
            if not node: continue
            if visited:
                out += [node.val]
            else:
                stack += [(node, True)]
                stack += [(node.right, False)]
                stack += [(node.left, False)]
        return out

Solution 2

There is another solution, where use almost the same routine as preorder traversal, but first visit left and then right. In the end reverse array. Time and space complexity is also O(n), but twice slower, because we need to reverse list in the end. Instead we can use deque for our result and add elements not to the end but to the beginning or out.

Complexity

Time and space complexity is O(n).

Code

class Solution:
    def postorderTraversal(self, root):
        if not root: return []
        stack, out = [root], []
        while stack:
            cur = stack.pop()
            out.append(cur.val)
            for child in filter(None, [cur.left, cur.right]):
                stack += [child]
        return out[::-1]