Python3 | Beats 95% | Iterative Level Order Traversal of a Tree
Intuition\nWhen dealing with a binary tree, it\'s often useful to traverse it in a level-order manner, which means visiting nodes level by level from left to ri
# Intuition\nWhen dealing with a binary tree, it\'s often useful to traverse it in a level-order manner, which means visiting nodes level by level from left to right. To accomplish this, we can use a data structure called a deque (double-ended queue), which allows us to efficiently add elements to the end and remove elements from the front. This is useful for traversing the tree in a breadth-first manner.\n\n# Approach\n**Initial State:**\n\n- We have a binary tree with a root node.\n- We have an empty list called "result" to store the level-order traversal.\n\n![Image 001.png](https://assets.leetcode.com/users/images/668df346-9692-4809-b81f-db7bf7587969_1692624601.251593.png)\n\n**Step 1: Initializing the Queue**\n\n- We create a deque called "queue" and initialize it with the root node.\n- The queue initially contains only the root node.\n\n![Image 002.png](https://assets.leetcode.com/users/images/1e30b095-3f5b-4464-9eb3-33fbad7fcbaa_1692624662.4974828.png)\n\n\n**Step 2: Performing Level-Order Traversal**\n\n- We start a loop that continues as long as the queue is not empty.\n- For each level, we maintain a list called "level_values" to store the values of nodes in that level.\n- We also track the size of the current level using "level_size".\n- We iterate through the nodes in the current level and process them.\n\n![Image 003.png](https://assets.leetcode.com/users/images/6b9fe280-a366-4ee5-b4a9-288e4084a5ff_1692624775.1803944.png)\n\n**Step 3: Processing Nodes in the Current Level**\n\n- We pop the first node (3) from the queue and add its value to the "level_values" list.\n- We enqueue the left and right children of the popped node (9 and 20) if they exist.\n\n![Image 004.png](https://assets.leetcode.com/users/images/a594f670-a897-4389-8011-4cb48176802b_1692624904.0614982.png)\n\n\n**Step 4: Moving to the Next Level**\n\n- We have finished processing the nodes in the current level.\n- We append the "level_values" list to the "result" list.\n- "level_values" is reset to an empty list.\n- We continue this process for each level in the tree.\n\n![Image 005.png](https://assets.leetcode.com/users/images/6cbe9e62-281c-42f7-a5c7-2edb2549f2fb_1692624968.7731628.png)\n\n\n**Step 5: Processing Nodes in the Second Level**\n\n- We pop the first node (9) from the queue and add its value to the "level_values" list.\n- The left and right children of node 9 are not present, so no nodes are enqueued.\n\n![Image 006.png](https://assets.leetcode.com/users/images/0b460d57-84a8-4935-8100-d7428adedc53_1692625014.8491945.png)\n\n**Step 6: Moving to the Next Level (Final Level)**\n\n- We have finished processing the nodes in the second level.\n- We append the "level_values" list to the "result" list.\n- "level_values" is reset to an empty list.\n\n![Image 007.png](https://assets.leetcode.com/users/images/e92ca919-a84f-4cbf-a482-3e2185876be5_1692625076.2025137.png)\n\n**Step 7: Processing Nodes in the Final Level**\n\n- We pop the first node (20) from the queue and add its value to the "level_values" list.\n- We enqueue the left and right children of node 20 (15 and 7).\n\n![Image 008.png](https://assets.leetcode.com/users/images/f0311d18-6bef-4b9a-afee-3c63b61cc8f4_1692625134.3149369.png)\n\n**Step 8: Finishing the Final Level**\n- We pop the first node (15) from the queue and add its value to the "level_values" list.\n- We pop the second node (7) from the queue and add its value to the "level_values" list.\n\n![Image 009.png](https://assets.leetcode.com/users/images/b85438ac-538c-4575-86b5-3b16e873f9f5_1692625279.38928.png)\n\n**Step 9: Completed Traversal**\n\n- The queue is now empty, indicating that we have processed all nodes in the tree.\n- The "level_values" list for the final level is appended to the "result" list.\n\n![Image 010.png](https://assets.leetcode.com/users/images/e23d245a-b790-4ef2-913f-ea5d5c130723_1692625344.447872.png)\n\n**Final Result:**\n\nThe level-order traversal of the binary tree is stored in the "result" list.\n\n![Image 011.png](https://assets.leetcode.com/users/images/87614fb9-d9ef-477a-b62e-ac9fb7f20f47_1692625407.425847.png)\n\n\n# Complexity\n- Time complexity:\n**O(n)**, where n is the number of nodes in the binary tree. We visit each node once.\n\n- Space complexity:\n**O(n)**, in the worst case, when the tree is completely unbalanced, the queue can hold all nodes in one level. Additionally, the result list will store the values of all nodes.\n\n# Code\n```\nfrom collections import deque\n\nclass Solution:\n    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n        result = []\n        if not root:\n            return result\n\n        # Initialize a queue with the root node\n        queue = deque([root])\n\n        # Perform level-order traversal\n        while queue:\n            level_values = []\n            level_size = len(queue)\n            for _ in range(level_size):\n                # Process the next node in the queue\n                node = queue.popleft()\n                level_values.append(node.val)\n                \n                # Enqueue the left child if it exists\n                if node.left:\n                    queue.append(node.left)\n                \n                # Enqueue the right child if it exists\n                if node.right:\n                    queue.append(node.right)\n            \n            # Add the values of the current level to the result\n            result.append(level_values)\n        \n        # Return the final level-order traversal result\n        return result\n\n```
['Tree', 'Breadth-First Search', 'Binary Tree', 'Python', 'Python3']