# C++ 0ms Recursive and Non-Recursive (DFS Stack) Solution

• Recursive solution recurses on left child, then right child, then adds the current node's value to the array.

The iterative solution uses depth-first search implemented with a stack. Nodes are added as a `pair<TreeNode*, bool>` with the bool set to false (it's children have not been added to the stack). If the pair at the top of the stack has bool == false, it adds the current pair, the right child pair and left child pair to the stack in that order (i.e. when popped, it will return left->right->parent); if bool == true then it adds the value to the array.

``````class Solution {
public:
void traverse(TreeNode* curr, vector<int> &vals) {  //recursive solution
if(curr != NULL) {
traverse(curr->left, vals);
traverse(curr->right, vals);
vals.push_back(curr->val);
}
}

vector<int> postorderTraversal(TreeNode* root) {
vector<int> vals;
if (root == NULL) return vals;

//traverse(root, vals);   //recursive solution

stack<pair<TreeNode*, bool>> dfs;   //iterative solution
dfs.push(pair<TreeNode*, bool>(root, false));
while (!dfs.empty()) {
pair<TreeNode*, bool> curr = dfs.top(); dfs.pop();
if (curr.first != NULL && curr.second == false) {
curr.second = true;
dfs.push(curr);
dfs.push(pair<TreeNode*, bool>(curr.first->right, false));
dfs.push(pair<TreeNode*, bool>(curr.first->left, false));
}
else if (curr.second == true) {
vals.push_back(curr.first->val);
}
}
return vals;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.