Binary Tree PreOrder Traversal - Beats upto 100% of other's runtime
Basic Concept\n Describe your first thoughts on how to solve this problem. \nA PreOrder Traversal is done in the order Root-Left-Right . \n\n---\n\n# Code Walk 
# Basic Concept\n<!-- Describe your first thoughts on how to solve this problem. -->\nA PreOrder Traversal is done in the order **Root-Left-Right** . \n\n---\n\n# Code Walk Through\n<!-- Describe your approach to solving the problem. -->\nLet\'s understand the code and approach.\n\n**Initializations**\n1. We initialize a stack which is going to hold our nodes in the preorder manner.\n\n2. An ArrayList is initialized that is going to be the final list .\n\nNow , if our root node is null , we need to handle that case as well .\nSo , we just return the empty output list .\n ```\nStack<TreeNode>stack = new Stack<>();\n        List<Integer>output = new ArrayList<>();\n        if(root==null)\n        {\n            return output;\n        }\n```\n\nNow, we push our root node to the stack , since root has to be processed first.\nAnd use a loop to traverse until our stack becomes empty.\n\n```\nTreeNode current = stack.pop();\n        output.add(current.val);\n\n        if(current.right!=null)\n        {\n            stack.push(current.right);\n        }\n\n        if(current.left!=null)\n        {\n            stack.push(current.left);\n        }\n\n```\nIn this part of the code , we set the current pointer with the popped element from the stack ( which was the root node itself) and then add it to the output list.\n\nthen we check if current node\'s right one is not null , we push that right node into the stack .\nSimilar steps with the current node\'s left child.\n\n**Why RightNode is processed before the LeftNode when the PreOrder Traversal is otherwise**?\n\n- because of stack\'s LIFO principle where the last element is popped first , so if we push left node after the right node , then left will get popped out from the stack first** . And then finally return the output list.\n---\n\n# Complexity\n- Time complexity : $$O(n)$$\n<!-- Add your time complexity here, e.g.  -->\n\n- Space complexity : $$O(n)$$\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        Stack<TreeNode>stack = new Stack<>();\n        List<Integer>output = new ArrayList<>();\n        if(root==null)\n        {\n            return output;\n        }\n      stack.push(root);\n\n      while(!stack.isEmpty()){\n        TreeNode current = stack.pop();\n        output.add(current.val);\n\n        if(current.right!=null)\n        {\n            stack.push(current.right);\n        }\n\n        if(current.left!=null)\n        {\n            stack.push(current.left);\n        }\n      }//while ends\n     return output;\n    }//function ends\n}//class ends\n```
['Stack', 'Tree', 'Depth-First Search', 'Binary Tree', 'Java']