✅ 🔥 0 ms Runtime Beats 100% User🔥||  Code Idea ✅ ||  Algorithm & Solving Step  ✅ ||
\n\n\u2705  IF YOU LIKE THIS SOLUTION, PLEASE UPVOTE AT THE END \u2705 :\n# I prefer Iterative Approach:\n\n### Intuition:\nPreorder traversal of a binary tree 
![Screenshot 2024-12-04 at 5.47.19\u202FAM.png](https://assets.leetcode.com/users/images/e1057879-14a1-4b5f-b514-60e4a12f1e46_1733271480.7984586.png)\n\n\u2705  IF YOU LIKE THIS SOLUTION, PLEASE UPVOTE AT THE END \u2705 :\n# I prefer Iterative Approach:\n\n### **Intuition:**\nPreorder traversal of a binary tree visits nodes in the following order:\n1. **Root** node.\n2. **Left subtree**.\n3. **Right subtree**.\n\nThis traversal is useful when you need to create a prefix notation or evaluate expressions stored in trees.\n\n---\n\n### **Approach 1: Recursive Solution**\nA straightforward way to implement preorder traversal is by using recursion.\n\n---\n\n### **Algorithm:**\n1. Start with the root node.\n2. Visit the root.\n3. Recursively traverse the left subtree.\n4. Recursively traverse the right subtree.\n\n---\n\n### **Steps in Code (Python, C++, Java)**\n\n#### **Python - Recursive Approach:**\n\n```python\nclass Solution:\n    def preorderTraversal(self, root: TreeNode) -> list[int]:\n        result = []\n        \n        def dfs(node):\n            if not node:\n                return\n            result.append(node.val)  # Visit root\n            dfs(node.left)           # Traverse left subtree\n            dfs(node.right)          # Traverse right subtree\n        \n        dfs(root)\n        return result\n```\n\n---\n\n#### **C++ - Recursive Approach:**\n\n```cpp\nclass Solution {\npublic:\n    vector<int> preorderTraversal(TreeNode* root) {\n        vector<int> result;\n        dfs(root, result);\n        return result;\n    }\n    \n    void dfs(TreeNode* node, vector<int>& result) {\n        if (!node) return;\n        result.push_back(node->val); // Visit root\n        dfs(node->left, result);     // Traverse left subtree\n        dfs(node->right, result);    // Traverse right subtree\n    }\n};\n```\n\n---\n\n#### **Java - Recursive Approach:**\n\n```java\nimport java.util.*;\nclass Solution {\n    public List<Integer> preorderTraversal(TreeNode root) {\n        List<Integer> result = new ArrayList<>();\n        dfs(root, result);\n        return result;\n    }\n    \n    private void dfs(TreeNode node, List<Integer> result) {\n        if (node == null) return;\n        result.add(node.val);       // Visit root\n        dfs(node.left, result);     // Traverse left subtree\n        dfs(node.right, result);    // Traverse right subtree\n    }\n}\n```\n\n---\n\n### **Approach 2: Iterative Solution Using Stack**\nTo avoid recursion, we can use a stack to mimic the function call stack.\n\n---\n\n### **Algorithm:**\n1. Initialize a stack with the root node.\n2. While the stack is not empty:\n   - Pop the node and visit it.\n   - Push its right child (if any).\n   - Push its left child (if any).\n3. Return the result.\n\n---\n\n#### **Python - Iterative Approach:**\n\n```python\nclass Solution:\n    def preorderTraversal(self, root: TreeNode) -> list[int]:\n        if not root:\n            return []\n        \n        stack = [root]\n        result = []\n        \n        while stack:\n            node = stack.pop()\n            result.append(node.val)  # Visit node\n            \n            if node.right:\n                stack.append(node.right)  # Push right child\n            if node.left:\n                stack.append(node.left)   # Push left child\n        \n        return result\n```\n\n---\n\n#### **C++ - Iterative Approach:**\n\n```cpp\n#include <vector>\n#include <stack>\nusing namespace std;\n\nclass Solution {\npublic:\n    vector<int> preorderTraversal(TreeNode* root) {\n        vector<int> result;\n        if (!root) return result;\n        \n        stack<TreeNode*> s;\n        s.push(root);\n        \n        while (!s.empty()) {\n            TreeNode* node = s.top();\n            s.pop();\n            result.push_back(node->val);  // Visit node\n            \n            if (node->right) s.push(node->right);  // Push right child\n            if (node->left) s.push(node->left);    // Push left child\n        }\n        return result;\n    }\n};\n```\n\n---\n\n#### **Java - Iterative Approach:**\n\n```java\nimport java.util.*;\n\nclass Solution {\n    public List<Integer> preorderTraversal(TreeNode root) {\n        List<Integer> result = new ArrayList<>();\n        if (root == null) return result;\n        \n        Stack<TreeNode> stack = new Stack<>();\n        stack.push(root);\n        \n        while (!stack.isEmpty()) {\n            TreeNode node = stack.pop();\n            result.add(node.val);  // Visit node\n            \n            if (node.right != null) stack.push(node.right);  // Push right child\n            if (node.left != null) stack.push(node.left);    // Push left child\n        }\n        \n        return result;\n    }\n}\n```\n\n---\n\n### **Time Complexity:**\n- **DFS (Recursive and Iterative)**: O(n), where n is the number of nodes in the tree. Each node is visited once.\n  \n### **Space Complexity:**\n- **Recursive DFS**: O(h), where h is the height of the tree (due to the call stack).\n- **Iterative DFS**: O(h), where h is the height of the tree (due to the stack).\n\n### **Example Walkthrough:**\nFor the input `root = [1, null, 2, 3]`, the traversal proceeds as:\n1. Visit `1`\n2. Move to the right, visit `2`\n3. Move to the left, visit `3`\n\nOutput: `[1, 2, 3]`.\n\n\n\n![image.png](https://assets.leetcode.com/users/images/afd4681f-a28a-438d-bdc1-a6f9dc6c4e3a_1733271763.5887356.png)\n
['Stack', 'Tree', 'C++', 'Java', 'Python3']