Skip to content
The Chat Archive
minimax-m1 LMArena Human Preference 140K

Implement breadth-first traversal (level-order) of a binary tree using a queue.

  1. User

    Implement breadth-first traversal (level-order) of a binary tree using a queue.

  2. Assistant

    To implement a breadth-first traversal (level-order) of a binary tree using a queue, follow these steps:

    1. Check for an empty tree: If the root is None, return an empty list.
    2. Initialize a queue: Start with the root node in the queue.
    3. 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 result
    

    Explanation:

    • Queue Usage: The deque efficiently 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} }

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.