✅[C++] EASY|| Beats100%  || 3 Approach With explaination✅
\uD83C\uDFA5\uD83D\uDD25 Exciting News! Join my Coding Journey! Subscribe Now! \uD83D\uDD25\uD83C\uDFA5\n\n\uD83D\uDD17 Link in the leetcode profile \n\nNew cod
\uD83C\uDFA5\uD83D\uDD25 Exciting News! Join my Coding Journey! Subscribe Now! \uD83D\uDD25\uD83C\uDFA5\n\n\uD83D\uDD17 Link in the leetcode profile \n\nNew coding channel alert! \uD83D\uDE80\uD83D\uDCBB Subscribe to unlock amazing coding content and tutorials. Help me reach 1K subs to start posting more videos! Join now! \uD83C\uDF1F\uD83D\uDCAA\n\nThanks for your support! \uD83D\uDE4F\n# Intuition\n3 ways to solve this problem\n\n# Approach\n**1.Recursive approach**\n  - Check if the current node is empty or Null.\n  - Display the data part of the root (or current node)\n  - Traverse the left subtree by recursively calling the preorder function.\n  - Traverse the right subtree by recursively calling the preorder function.\n  \n**2.Iterative approach**\n  - Create an empty stack and push the root node to it.\n  - Do the following while the stack is not empty\n      1. Pop the top item from the stack and display it.\n      2. Push the right child of the popped item to the stack.\n      3. Push the left child of the popped item to the stack.\n# Complexity\n   - **Time complexity**:O(N)\n   - **Space complexity**:O(H)H=height of binary tree\n\n  **3.Morris traversal**\n - Initialize current as root\n - While current is not null:\n     1. If current does not have a left child:\n          (i) Print current\'s data.\n          (ii) Go to the right, i.e., current = current.right\n     2. Else:\n           (i)Make current as the right child of the rightmost node in current\'s left subtree.\n           (ii)Go to this left child, i.e., current = current.left.\n\n# Complexity\n- **Time complexity**:O(N)\n- **Space complexity**:O(1)\n\n\n \n![oms.png](https://assets.leetcode.com/users/images/f5a39b74-fd4e-4f2c-bfb2-7737e7f09f35_1673225202.6658852.png)\n\n# Code(Recursuve approach)\n```\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode() : val(0), left(nullptr), right(nullptr) {}\n *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}\n * };\n */\nclass Solution {\npublic:\n    vector<int>ans;\n    vector<int> preorderTraversal(TreeNode* root) {\n        if(root){\n            ans.push_back(root->val);\n            preorderTraversal(root->left);\n            preorderTraversal(root->right);\n        }\n        return ans;\n    }\n};\n```\n# Code(iterative approach)\n```\nclass Solution {\npublic:\n    vector<int> preorderTraversal(TreeNode* root) {\n        vector<int> ans;\n        stack<TreeNode*>st;\n        while (root || !st.empty()) {\n            if (root) {\n                ans.push_back(root -> val);\n                if (root -> right) {\n                    st.push(root -> right);\n                }\n                root = root -> left;\n            } else {\n                root = st.top();\n                st.pop();\n            }\n        }\n        return ans;\n    }\n};\n```\n# Code(Morris approach)\n```\nclass Solution {\npublic:\n    vector<int> preorderTraversal(TreeNode* root) {\n        vector<int> nodes;\n        while (root) {\n            if (root -> left) {\n                TreeNode* pre = root -> left;\n                while (pre -> right && pre -> right != root) {\n                    pre = pre -> right;\n                }\n                if (!pre -> right) {\n                    pre -> right = root;\n                    nodes.push_back(root -> val);\n                    root = root -> left;\n                } else {\n                    pre -> right = NULL;\n                    root = root -> right;\n                }\n            } else {\n                nodes.push_back(root -> val);\n                root = root -> right;\n            }\n        }\n        return nodes;\n    }\n};\n```\n\nIf you really found my solution helpful **please upvote it**, as it motivates me to post such kind of codes.\n*Let me know in comment if i can do bette*r.\nLets connect on [LINKDIN](https://www.linkedin.com/in/mahesh-vishnoi-a4a47a193/).\n\n
['Stack', 'Recursion', 'C++']