Python RECURSIVE and ITERATIVE Solutions
Upvote if you thought this code was helpful!\n\nJoin our discord to meet other people preparing for interviews!\nhttps://discord.gg/Aj2uT5rP\n\nRecursive Pre-Or
**Upvote** if you thought this code was helpful!\n\n**Join our discord** to meet other people preparing for interviews!\n**https://discord.gg/Aj2uT5rP**\n\n**Recursive Pre-Order Traversal**\n```python\nclass Solution:\n    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n        ans = []\n        \n        def dfs(node, depth):\n            if not node:\n                return\n            if depth >= len(ans):\n                ans.append([])\n            ans[depth].append(node.val)\n            dfs(node.left, depth + 1)\n            dfs(node.right, depth + 1)\n        \n        dfs(root, 0)\n        return ans\n```\n**Time Complexity**: O(n)\n**Space Complexity**: O(n) for `ans` array. O(h) for recursive call stack, which is worst case O(n).\n\n**Iterative Level-Order Traversal**\n```python\nclass Solution:\n    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n        if not root:\n            return []\n        \n        ans = []\n        q = deque([root])\n        while q:\n            length = len(q)\n            ans.append([])\n            for _ in range(length):\n                node = q.popleft()\n                ans[-1].append(node.val)\n                if node.left:\n                    q.append(node.left)\n                if node.right:\n                    q.append(node.right)\n        return ans\n```\n**Time Complexity**: O(n)\n**Space Complexity**: O(n) for `ans` array. O(level) for the deque, which is worst case O(n).
['Tree', 'Iterator', 'Python']