minimax-m1 LMArena Human Preference 140K
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
To implement a breadth-first traversal (level-order) of a binary tree using a queue, follow these steps:
- Check for an empty tree: If the root is
None, return an empty list. - Initialize a queue: Start with the root node in the queue.
- Process nodes level by level:
- Dequeue a node, add its value to the result.
- Enqueue its left and right children (if they exist).
Here's the Python code:
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 level_order(root): if not root: return [] result = [] queue = deque([root]) while queue: node = queue.popleft() result.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) return resultExplanation:
- Queue Usage: The
dequeefficiently allows popping from the front (FIFO behavior). - Level-Order Logic: Nodes are visited level by level, starting from the root, then left to right at each subsequent level.
\boxed{ \begin{aligned} &\text{Level-order traversal using a queue ensures nodes are visited level by level, left to right.} \end{aligned} }
- Check for an empty tree: If the root is
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.