Close Menu
    Code and Debug
    • Home
    • Our Courses
    • Blog
    • About Us
    • Contact Us
    Facebook X (Twitter) Instagram YouTube WhatsApp
    • Home
    • Our Courses
    • Blog
    • About Us
    • Contact Us
    Facebook Instagram YouTube LinkedIn WhatsApp
    Code and Debug – BlogCode and Debug – Blog
    Code and Debug – BlogCode and Debug – Blog
    Home»Data Structures & Algorithms»Breadth-First Search in Binary Trees: Level-Order Traversal with Python
    Data Structures & Algorithms

    Breadth-First Search in Binary Trees: Level-Order Traversal with Python

    codeanddebugBy codeanddebug12 May 2025Updated:14 May 2025No Comments4 Mins Read
    Share Facebook Twitter Pinterest LinkedIn Tumblr Reddit Telegram Email
    breadth first search featured image
    Share
    Facebook Twitter LinkedIn Pinterest Email

    Learn how to perform a level-order (BFS) traversal on a binary tree using Python’s collections.deque. This beginner-friendly guide shows you step-by-step code, intuition, and real examples, perfect for LeetCode prep!

    Content:
     [show]
    • Why Level-Order Traversal?
    • Intuition & Approach
    • Code Implementation
    • Code Explanation
    • Dry Run (Example)
    • Time and Space Complexity
    • Conclusion

    Why Level-Order Traversal?

    If Depth-First Search (DFS) is like diving deep down one path of a maze, Breadth-First Search (BFS) is like exploring each floor of a building one level at a time. In a binary tree, BFS lets us visit all nodes at depth 0 (the root), then depth 1 (its children), then depth 2, and so on.

    Level-order traversal (BFS) is the go-to technique for:

    • Finding the shortest path in unweighted graphs or trees.
    • Printing a tree level by level (nice for debugging!).
    • Solving problems like “Zigzag Level Order” or “Average of Levels” on LeetCode.

    We’ll use Python’s collections.deque as our queue (fast appends/pops) and build a result list of lists, one sublist per level.

    Also read about the Python Program to Find Maximum Depth of a Binary Tree.

    Intuition & Approach

    1. Start at the root.
    2. Use a queue to hold nodes of the current level.
    3. While the queue isn’t empty:
      • Note the current queue size (level_size), that’s how many nodes are on this level.
      • Dequeue each node, record its value.
      • Enqueue its children (left then right) for the next level.
      • After processing level_size nodes, you’ve finished one level—append the collected values to result.

    This approach ensures we visit nodes in perfect left-to-right, level-by-level order.


    Code Implementation

    from collections import deque
    
    def level_order_traversal(root):
        """
        Perform a BFS (level-order) traversal on a binary tree and
        return a list of levels, where each level is a list of node values.
        """
        result = []
        if not root:
            return result
    
        queue = deque([root])
    
        while queue:
            level_size = len(queue)
            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

    Code Explanation

    • Initialize:
      • result = [] will hold our final list of levels.
      • If root is None, return [] immediately.
    • Setup Queue:
      • queue = deque([root]) seeds the BFS with the root node.
    • Main Loop:
      • While queue has nodes, note level_size = len(queue).
      • Create an empty current_level = [] to collect this level’s values.
    • Process One Level:
      • Loop level_size times:
        1. node = queue.popleft() dequeues the next node.
        2. current_level.append(node.val) records its value.
        3. If node.left exists, queue.append(node.left).
        4. If node.right exists, queue.append(node.right).
    • Save Level:
      • After the for-loop, current_level holds all values for one depth—append it to result.
    • Continue:
      • The next iteration processes the next depth, until the queue is empty.

    Dry Run (Example)

    Given the tree:

          1
         / \
        2   3
       / \   \
      4   5   6
    • Start: queue = [1]
    • Level 0:
      • level_size = 1.
      • Dequeue 1 → current_level = [1].
      • Enqueue 2, 3.
      • Append [1] to result.
    • Level 1:
      • queue = [2, 3], level_size = 2.
      • Dequeue 2 → [2], enqueue 4,5.
      • Dequeue 3 → [2,3], enqueue 6.
      • Append [2,3].
    • Level 2:
      • queue = [4,5,6], level_size = 3.
      • Dequeue 4 → [4]. No children.
      • Dequeue 5 → [4,5]. No children.
      • Dequeue 6 → [4,5,6]. No children.
      • Append [4,5,6].
    • Done: queue empty.

    Final result: [[1], [2,3], [4,5,6]]


    Time and Space Complexity

    • Time Complexity:
      • We visit each of the N nodes exactly once → O(N).
    • Space Complexity:
      • The queue may hold up to the entire width of the tree (worst case, N/2 nodes at the lowest level) → O(N).
      • The result list stores all values → O(N).

    Conclusion

    Level-order traversal via BFS is incredibly powerful for problems that need to process nodes by depth. Python’s deque keeps it elegant and efficient. Whether you’re printing a tree level by level, finding the shortest path, or prepping for LeetCode’s “Binary Tree Zigzag” question, mastering this pattern is a must-have in your toolkit.

    Master DSA with our course

    For any changes to the document, kindly email at code@codeanddebug.in or contact us at +91-9712928220.

    Binary Trees
    Share. Facebook Twitter Pinterest LinkedIn Tumblr Email
    Previous ArticleA Beginner’s Guide to Preorder, Inorder & Postorder Traversals
    Next Article Maximum Depth of Binary Tree | Explained with Examples
    codeanddebug
    • Website

    Related Posts

    Data Structures & Algorithms

    Detect Cycle in a Directed Graph – Kahn’s Algorithm (BFS Topological Check) in Python

    4 June 2025
    Data Structures & Algorithms

    Topological Sort (Kahn’s Algorithm) – Simple BFS Solution in Python

    4 June 2025
    Data Structures & Algorithms

    Detect Cycle in a Directed Graph

    3 June 2025
    Add A Comment
    Leave A Reply Cancel Reply

    Categories
    • Data Structures & Algorithms (38)
      • Beginner (17)
      • Expert (7)
      • Intermediate (14)
    • Uncategorised (1)
    Recent Posts

    Detect Cycle in a Directed Graph – Kahn’s Algorithm (BFS Topological Check) in Python

    4 June 2025

    Topological Sort (Kahn’s Algorithm) – Simple BFS Solution in Python

    4 June 2025

    Detect Cycle in a Directed Graph

    3 June 2025

    Topological Sort in Graph | Simple DFS + Stack Solution in Python

    3 June 2025

    Is Graph Bipartite? | Leetcode 785 | Easy 2-Color DFS Solution in Python

    1 June 2025
    Facebook Instagram YouTube LinkedIn WhatsApp
    © 2025 Code and Debug. All rights reserved.

    Type above and press Enter to search. Press Esc to cancel.