Skip to content
TheChatArchiveThe Chat Archive
Claudeclaude-sonnet-4-20250514· AnthropicHugging Face LMArena Human Preference 140K

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

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with MiniMaxminimax-m1’s answer.
  1. User

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

  2. Claude 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:

    1. Start with the root node in the queue
    2. 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 deque from 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.

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