✅C++ || Three Solutions || Recursive , Iterative , Morris Traversal
Approach 1\nRecursive Traversal \n# Complexity\n- Time complexity : O(n)\n- Space complexity: O(n) (Function Call Stack)\n# Code\n\nclass Solution {\n    void t
# Approach 1\nRecursive Traversal \n# Complexity\n- Time complexity : $$O(n)$$\n- Space complexity: $$O(n)$$ (Function Call Stack)\n# Code\n```\nclass Solution {\n    void traverse(TreeNode* root,vector<int>& ans)\n    {\n        if(root==NULL)return;\n        \n        ans.push_back(root->val);\n        traverse(root->left,ans);\n        traverse(root->right,ans);\n    }\n    \npublic:\n    vector<int> preorderTraversal(TreeNode* root) \n    {\n        vector<int> ans;\n        traverse(root,ans);\n        return ans;\n        \n    }\n};\n```\n\n# Approach 2\nIterative Traversal with Stack \n# Complexity\n- Time complexity : $$O(n)$$\n- Space complexity: $$O(n)$$ (Stack space)\n# Code\n```\nclass Solution {\npublic:\n    vector<int> preorderTraversal(TreeNode* root) {\n        vector<int>ans;\n        stack<TreeNode*>st;\n        \n        if(root==NULL) return ans;\n        st.push(root);\n        \n        while(!st.empty())\n        {\n            TreeNode *node=st.top();\n            st.pop();\n            \n            if(node->right!=NULL) st.push(node->right);\n            if(node->left!=NULL) st.push(node->left);\n        \n            ans.push_back(node->val);\n        }\n        return ans;\n    }\n};\n```\n# Approach 3\nMorris Traversal \n# Complexity\n- Time complexity : $$O(n)$$\n- Space complexity: $$O(1)$$ \n# Code\n```\nclass Solution {\npublic:\n    vector<int> preorderTraversal(TreeNode* root) \n{\n        vector<int>ans;\n        TreeNode* curr=root;\n        \n        while(curr!=NULL)\n        {\n            if(curr->left==NULL)\n            {\n                ans.push_back(curr->val);\n                curr=curr->right;\n            }\n            else\n            {\n                TreeNode* prev=curr->left;\n                \n                while(prev->right!=NULL && prev->right!=curr)\n                {\n                    prev=prev->right;\n                }\n\n                if(prev->right==NULL)\n                {\n                    prev->right=curr;\n                    ans.push_back(curr->val);\n                    curr=curr->left;\n                }\n                else\n                {\n                    prev->right=NULL;\n                    curr=curr->right;\n                }\n            }\n        }\n        return ans;\n    }\n};\n```
['Stack', 'Tree', 'Depth-First Search', 'Binary Tree', 'C++']