[C++] 100% Time - DFS Recursive vs. Iterative Solutions Explained and Compared
First in the easy, convenient way of a plain DFS: we just move left as much as possible, update res at each step and only then we have met the last left branch 
First in the easy, convenient way of a plain DFS: we just move `left` as much as possible, update `res` at each step and only then we have met the last `left` branch on our current path we start considering going to the `right`:\n\n```cpp\nclass Solution {\npublic:\n    vector<int> res;\n    void dfs(TreeNode *root) {\n        if (!root) return;\n        res.push_back(root->val);\n        dfs(root->left);\n        dfs(root->right);\n    }\n    vector<int> preorderTraversal(TreeNode* root) {\n        dfs(root);\n        return res;\n    }\n};\n```\n\nThe iterative solution does not take too much effort either, it is just potentially less intuitive; let\'s go with a DFS for this one as well, since going for a BFS would require needless extra complexity and more logic as we go (in other words: the interviewer should really hate you for that); the structure will be similar: class accumulator variable `res`, no external helper function needed for this one and nice loop inside to build the result.\n\nWe start checking if the tree is empty, in which case we just return our `res`, empty as well. If not, we declare a stack `s` and initialise it with a first push, `root` itself.\n\nNow the fun begins: we loop while our stack is not empty, we pop the last element, we add back its possible child - but not that we add `right` first, `left` second, since in a stack the values come out following a LIFO approach.\n\nTry to visualise it with the example tree of any other one you might wish to build; use pen and paper if not sure, but it works :)\n\nOnce the stack is empty, we are done: time to return `res`.\n\nThe code:\n\n```cpp\nclass Solution {\npublic:\n    vector<int> res;\n    vector<int> preorderTraversal(TreeNode* root) {\n        if (!root) return res;\n        stack<TreeNode*> s;\n        s.push(root);\n        TreeNode *currNode;\n        while (s.size()) {\n            currNode = s.top();\n            s.pop();\n            res.push_back(currNode->val);\n            if (currNode->right) s.push(currNode->right);\n            if (currNode->left) s.push(currNode->left);\n        }\n        return res;\n    }\n};\n```
['Depth-First Search', 'Recursion', 'C', 'Iterator', 'C++']