 Given the root of a tree `root`, return an array containing the postorder traversal of the tree. Write the solution using iterative code - do not use recursion. Here's the code for a recursive inorder traversal: ``` traversal = [] def visitAll(node): if node is None: base case return visitAll(node.left) visitAll(node.right) traversal.append(node.val) ``` In this problem, we need to write the same code but without using a recursive function. As usual, this means you need to implement the recursi

Iterative Postorder Traversal




-----problem-----

Given the root of a tree `root`, return an array containing the postorder traversal of the tree. 

Write the solution using iterative code - do not use recursion.



\image{2}


-----solution-----

Here's the code for a \i{recursive} inorder traversal:
```

traversal = []

def visitAll(node):
    if node is None: # base case
        return
    visitAll(node.left)
    visitAll(node.right)
    traversal.append(node.val)
```


In this problem, we need to write the same code but without using a recursive function.
As usual, this means you need to implement the recursive code using your own stack, instead of using the computer's Call Stack.


The trick to doing this is keep track of whether you're visiting each node for the first time. The first time you visit a node, you should not act on the node, and should instead first run visitAll on the node's left and right children, and then come back to the current node. The next time you visit a node, you're ready to act on it (add it to the traversal).

Here's the code:

\answer



\tc $O(n)$

\sc $O(n)$  The `stack` takes up as much space as the Call Stack would have if we wrote this recursively, since the stack is just our own version of the Call Stack. This means `stack` can get $n$ calls deep, requiring $O(n)$ space.

Recursion

Iterative Postorder Traversal