Implement breadth-first traversal (level-order) of a binary tree using a queue.
- User
Implement breadth-first traversal (level-order) of a binary tree using a queue.
Assistant
Here's an implementation of breadth-first traversal for a binary tree using a queue:
from collections import deque class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def breadth_first_traversal(root): """ Performs breadth-first (level-order) traversal of a binary tree. Args: root: TreeNode - The root of the binary tree Returns: list: Values of nodes in level-order """ if not root: return [] result = [] queue = deque([root]) while queue: node = queue.popleft() result.append(node.val) # Add children to queue (left first, then right) if node.left: queue.append(node.left) if node.right: queue.append(node.right) return result def breadth_first_by_levels(root): """ Alternative implementation that returns nodes grouped by level. Args: root: TreeNode - The root of the binary tree Returns: list of lists: Each inner list contains values from one level """ if not root: return [] result = [] queue = deque([root]) while queue: level_size = len(queue) current_level = [] # Process all nodes at current level for _ in range(level_size): node = queue.popleft() current_level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(current_level) return result # Example usage if __name__ == "__main__": # Create a sample binary tree: # 3 # / \ # 9 20 # / \ # 15 7 root = TreeNode(3) root.left = TreeNode(9) root.right = TreeNode(20) root.right.left = TreeNode(15) root.right.right = TreeNode(7) # Standard breadth-first traversal print("Level-order traversal:", breadth_first_traversal(root)) # Output: [3, 9, 20, 15, 7] # Grouped by levels print("By levels:", breadth_first_by_levels(root)) # Output: [[3], [9, 20], [15, 7]]Key Points:
Algorithm Steps:
- Start with the root node in the queue
- While the queue is not empty:
- Dequeue a node and process it (add to result)
- Enqueue its left child (if exists)
- Enqueue its right child (if exists)
Time Complexity: O(n) where n is the number of nodes Space Complexity: O(w) where w is the maximum width of the tree (worst case O(n) for a complete binary tree)
The
dequefrom Python's collections module provides efficient O(1) operations for both ends, making it ideal for queue operations. The second implementation shows how to group nodes by their level, which is useful for problems that need level-specific processing.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.