Iterative Solution with Stack ✅Beats 100% solution in time✅
Intuition\nWe have to do preorder traversal where we print value for root then we go for it\'s left sub tree and in the last we go for right sub tree of the roo
# Intuition\nWe have to do preorder traversal where we print value for root then we go for it\'s left sub tree and in the last we go for right sub tree of the root.\n\nstack is the LIFO(Last in first out data structure) so we can use this property\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1-Add root of the tree in the stack and traverse till stack becomes empty \n2-Remove top of the stack and store it in the variable called rem now add value of rem in our List\n3-If there exist right child of the remove node (rem) then add it to the stack and then do same with the left child of the root \n\n(Here we are adding right child first and left child later so that while we will remove the element, left child will be poped out first )\n\n# Complexity\n- Time complexity:O(N)\nWe are Traversing all elements of the tree ones so that time complexity will be O(n)<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(H)\n-Here H is the height of the tree (Stack will not store all n elements at once)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n/**\n * Definition for a binary tree node.\n * public class TreeNode {\n *     int val;\n *     TreeNode left;\n *     TreeNode right;\n *     TreeNode() {}\n *     TreeNode(int val) { this.val = val; }\n *     TreeNode(int val, TreeNode left, TreeNode right) {\n *         this.val = val;\n *         this.left = left;\n *         this.right = right;\n *     }\n * }\n */\nclass Solution {\n    public List<Integer> preorderTraversal(TreeNode root) {\n        if(root==null){\n            return new ArrayList<>();\n        }\n        List<Integer>l = new ArrayList<>();\n        Stack<TreeNode>st = new Stack<>();\n        st.push(root);\n        while(st.isEmpty()==false){\n            TreeNode rem = st.pop();\n            l.add(rem.val);\n            if(rem.right!=null){\n                st.push(rem.right);\n            }\n            if(rem.left!=null){\n                st.push(rem.left);\n            }\n        }\n        return l;\n    }\n}\n```\nI hope you understand the solution, have a great day ahead.\nHar Har Mahadev\uD83D\uDD49\uFE0F\u2764\uFE0F,\n
['Java']