[C++] DFS Iterative vs. Recursive Solutions Compared and Explained, ~99% Time, ~99% Space
The normal iterative approach for a DFS algorithm presumes that you have a stack and progressively add the children as you go down a branch, while doing some op
The normal iterative approach for a DFS algorithm presumes that you have a stack and progressively add the children as you go down a branch, while doing some operation (in our case extracting `val`), as you go with the current top of the stack that you will pop.\n\nOnce you have nothing more to add, it means no more children there - you reached a leaf and so, keeping popping out of the stack, you will backtrack to some previous node.\n\nIt is a convenient approach, with the sole caveat that it will give you results in a top-down fashion (you start from the top and then proceed adding its children down); also, if you were to look for a specific order (say, left branches first), you would have to push them into the stack so that the ones you want parsed first (left, in our example) are pushed last.\n\nThat said, this problem requires us to extact the *postorder* traversal, so, in order to make it work, we will have to reverse the order of our result before returning it.\n\nNow, the way I did it: first of all we get rid of a possible edge case - an empty tree, in which case we return an empty vector.\n\nIf we are still in the function, then we declare a bunch of support variable, this time (almost) all of a different kind:\n* our usual accumulator variable `res`, initially an empty vector of integers;\n* `pos`, an int that will help us move through our "stack";\n* `stackArray`, which, as the name implies, is not really a stack, but just an array of pointers used as a stack, with an initial size of `1000` (you might set it to the maximum number of nodes which is 10x, but that would be necessary if they were all on a line and with a bit of experimentation, you will see the rarely you need more than that to pass all the tests);\n* not strictly needed, but just for convenience I also declared `curr`, that we will use to store the value of the currently parsed node.\n\nWe will proceed to put `root` into `stackArray` increasing `pos`, then, as described, we will pop and extract `curr` out by reducing `pos`, the value `val` of `curr` into `res` and finally keep pushing the children of the current node `curr` into `stackArray`.\n\nOnce we are done, we `reverse` `res` and can return it :)\n\nThe iterative code:\n\n```cpp\nclass Solution {\npublic:\n    vector<int> postorder(Node* root) {\n        // edge case out of the way\n        if (!root) return {};\n        // support variables\n        vector<int> res;\n        int pos = 0;\n        Node *stackArray[1000], *curr;\n        stackArray[pos++] = root;\n        // DFS - iteration on!\n        while (pos) {\n            curr = stackArray[--pos];\n            res.push_back(curr->val);\n            for (Node *n: curr->children) stackArray[pos++] = n;\n        }\n        reverse(begin(res), end(res));\n        return res;\n    }\n};\n```\n\nNow, for the other, canonical approach, we just have a simpler structure: we declare `res` as a class variable, then in our main function we just call the helper function `dfs` (provided `root != NULL`, so we have to check for it only once) and return `res` when the helper is done running.\n\nBut does `dfs` do?\n\npretty simple as well: it calls itself recursively on all the children (if any) of the current `root` and then pushed its value `val` into `res` - notice that order matters and you will want to push only after calling all the recursive calls, so that it acts as a sort of backtracking trick.\n\nThe recursive code, which seems to be a bit faster and a bit more memory consuming:\n\n```cpp\nclass Solution {\npublic:\n    vector<int> res;\n    void dfs(Node *root) {\n        for (int i = 0, len = root->children.size(); i < len; i++) dfs(root->children[i]);\n        res.push_back(root->val);\n    }\n    vector<int> postorder(Node *root) {\n        if (root) dfs(root);\n        return res;\n    }\n};\n```\n\nIf you want to practice more in this sense, consider [this problem](https://leetcode.com/problems/n-ary-tree-level-order-traversal/) and [my solution for it](https://leetcode.com/problems/n-ary-tree-level-order-traversal/discuss/865601/).
['Depth-First Search', 'Recursion', 'C', 'Iterator', 'C++']