A recursive solution is very simple, it just recurses into the left node then recurses into the right node and then handles the current node.
The iterative solution is more difficult to come up with. The trick with iterative is that we need extra information in the stack entries. I used an extra bool flag to indicate whether we’ve handled (pushed) the nodes children. As we go around our loop we check whether the top stack entry has had its children handled and if not then we add the children (right first then left) to the stack and mark it that the children are handled. Otherwise if the top stack node has had its children handled already then we deal with this node, i.e. we add its value to the result vector and pop it from the stack. We have to use this handled children flag as we need to deal with the left children first and then leave the right children for later.
