Three types of solution(recursion, iterative,morris) 100% faster c++
All Three types of solutions: \n1. Recursion => TC - O(N) and SC - (N)\n2. Iterative => TC - O(N) and SC - (N)\n3. Morris Traversal => TC - O(N) and SC - (1)\n\
## All Three types of solutions: \n1. Recursion => TC - O(N) and SC - (N)\n2. Iterative => TC - O(N) and SC - (N)\n3. Morris Traversal => TC - O(N) and SC - (1)\n\n#### **Using recursion (4ms time) TC - O(N) and SC - O(N)**\n```\nclass Solution {\npublic:\n     vector<int> ans;\n     vector<int> preorderTraversal(TreeNode* root) {\n         if(root==NULL)return ans;\n\t\t ans.push_back(root->val);\n         preorderTraversal(root->left);\n         preorderTraversal(root->right);\n         return ans;\n     }\n}; \n```\n#### Iterative method using Stack(0ms) \n\n```\nclass Solution {\npublic:\n    vector<int> preorderTraversal(TreeNode* root) {\n        vector<int> ans;\n        stack<TreeNode*> store;\n        while(!store.empty() || root){\n            if(root){\n                ans.push_back(root->val); // print root\n                if(root->right){ \n                    store.push(root->right);//put into stack so that after print left we can go right\n                }\n                root=root->left; // make root of left sub tree;\n            }\n            else{\n                root=store.top();//if root is null that means left tree is not there; we pop the node\n                store.pop();\n            }\n        }\n\t\t return ans;\n    }\n};\n```\n\n#### **Morris Traversal in O(1) space and O(N) time**\n```\nclass Solution {\npublic:\n    vector<int> preorderTraversal(TreeNode* root) {\n        vector<int> ans;\n        while(root){\n            if(root->left==NULL){ // if left not there, add root to answer\n                ans.push_back(root->val);\n                root=root->right; // go to right (bcz left is not there)\n            }\n            else{  // left is there then find the predecessor of root(for tracking to root after visiting left)\n                TreeNode* temp = root;\n                temp=temp->left;\n                while(temp->right && temp->right!=root){\n                    temp = temp->right;\n                }\n                if(temp->right==NULL){  //link predecessor->right to root(to go to root)\n                    temp->right=root;\n                    ans.push_back(root->val); // push the root node (we are going in left direction so before that add root as ans);\n                    root=root->left;// goto left direction \n                }\n                else{ // if predecessor is linked with root that means left subtree is already visited; goto right \n                    temp->right=NULL;\n                    root=root->right;\n                }    \n            }\n        }\n        return ans;\n    }\n};\n```\n\n### **If you like the solution please upvote it. Thanks**\n
['Recursion', 'C', 'Iterator', 'C++']