C# Recursive and Iterative (using Stack) with explanation
Pre-order traversal is to visit the root first. Then traverse the left subtree. Finally, traverse the right subtree. \n> Preorder: visit > left > right\n\nItera
Pre-order traversal is to visit the root first. Then traverse the left subtree. Finally, traverse the right subtree. \n> Preorder: **visit > left > right**\n\n**Iterative Approach**\n* We need to use a `Stack` to remember the sub-trees as we go deeper\n* Since `stack`s are `first-in-last-out` approach, we need to:\n\t* **Visit**:  Add the node to the `list`\n\t* `Push` the `right sub-tree` first, then\n\t* `Push` the `left sub-tree`\n* So, when we `pop` the stack, \n\t* We get the `left sub-tree` first *before* the `right sub-tree` since it\'s pushed last\n\n```csharp\npublic class Solution {\n    public IList<int> PreorderTraversal(TreeNode root) {\n        IList<int> preorder = new List<int>();\n        \n        Stack<TreeNode> stack = new Stack<TreeNode>();\n        TreeNode node = root;\n        \n        if (node != null)\n            stack.Push(node);\n        \n        // visit > left > right\n        while (stack.Count > 0) {\n            node = stack.Pop();\n            preorder.Add(node.val); // Visit\n            \n            if (node.right != null) { // Push right\n                stack.Push(node.right);\n            }\n            \n            if (node.left != null) { // Push left\n                stack.Push(node.left);\n            }\n            \n        }\n        \n        return preorder;\n    }\n}\n```\n\n**Recursive Approach**\n* Recursion is the straightforward approach and mimics the concept of `visit > left > right` for `preorder` traversals\n* We need to pass the `list` as a parameter so we can add the values of the visited nodes to it\n* **Alternative approach**: instead of passing `preorder` list, you can make it a `global` field. \n* **Another approach**: final approach would be for the helper function to `return` the `preorder` list\n\n``` csharp\npublic class Solution {\n    public IList<int> PreorderTraversal(TreeNode root) { \n        IList<int> preorder = new List<int>();\n        PreOrder(preorder, root);\n        \n        return preorder;\n    }\n    \n    private void PreOrder(IList<int> list, TreeNode node) {\n        if (node == null) return;\n        \n        list.Add(node.val);         // Visit\n        PreOrder(list, node.left);  // Left\n        PreOrder(list, node.right); // Right\n    }\n}\n```
['Stack', 'Recursion', 'Iterator', 'C#']