Proper Tree Traversal || DFS || Python Easy || Begineer Friendly ||
Intuition\n Describe your first thoughts on how to solve this problem. \n- The intuition here is to perform a preorder traversal of a binary tree and collect th
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- The intuition here is to perform a preorder traversal of a binary tree and collect the values of the nodes in a list as you traverse the tree.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- We can implement a recursive approach to perform a preorder traversal of the tree.\n- Initialize an empty list `arr` to store the values of the nodes in the preorder traversal.\n- Start the traversal from the root node. If the node is not None, append its value to `arr`, and then recursively traverse its left and right subtrees.\n- Return the `arr` list containing the preorder traversal values.\n\n# Complexity\n- Time complexity:\n  - The time complexity of this approach is $$O(n)$$, where n is the number of nodes in the binary tree. This is because we visit each node exactly once during the traversal.\n- Space complexity:\n  - The space complexity is also $$O(n)$$ due to the space used by the `arr` list to store the traversal values. In the worst case, the list will contain all the nodes\' values.\n\n# Code\n```python\n# Definition for a binary tree node.\n# class TreeNode:\n#     def __init__(self, val=0, left=None, right=None):\n#         self.val = val\n#         self.left = left\n#         self.right = right\n\nclass Solution:\n    def __init__(self):\n        self.arr = []\n\n    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:\n        if root is not None:\n            self.arr.append(root.val)\n            self.preorderTraversal(root.left)\n            self.preorderTraversal(root.right)\n        return self.arr\n```
['Stack', 'Tree', 'Depth-First Search', 'Binary Tree', 'Python', 'Python3']