Tree Traversal Level Order BFS in DSA Python

Mental Model

Visit tree nodes level by level from top to bottom, left to right, like reading lines in a book.

Analogy: Imagine a group of friends standing in rows. You greet all friends in the first row before moving to the next row.

      1
     / \
    2   3
   / \   \
  4   5   6

Queue: []
Output: []

Dry Run Walkthrough

Input: Binary tree: 1 with children 2 and 3; 2 has children 4 and 5; 3 has child 6

Goal: Print nodes level by level: 1, then 2 and 3, then 4, 5, and 6

Step 1: Start with root node 1 in queue

Queue: [1]
Output: []

Why: We begin traversal from the root

Step 2: Remove 1 from queue, add to output, enqueue children 2 and 3

Queue: [2, 3]
Output: [1]

Why: Visit root first, then prepare to visit its children

Step 3: Remove 2 from queue, add to output, enqueue children 4 and 5

Queue: [3, 4, 5]
Output: [1, 2]

Why: Visit next node in level, then its children

Step 4: Remove 3 from queue, add to output, enqueue child 6

Queue: [4, 5, 6]
Output: [1, 2, 3]

Why: Continue level order visiting nodes and their children

Step 5: Remove 4 from queue, add to output, no children to enqueue

Queue: [5, 6]
Output: [1, 2, 3, 4]

Why: Leaf node visited, no children to add

Step 6: Remove 5 from queue, add to output, no children to enqueue

Queue: [6]
Output: [1, 2, 3, 4, 5]

Why: Leaf node visited, no children to add

Step 7: Remove 6 from queue, add to output, no children to enqueue

Queue: []
Output: [1, 2, 3, 4, 5, 6]

Why: Last node visited, traversal complete

Result:

Queue: []
Output: [1, 2, 3, 4, 5, 6]

Annotated Code

DSA Python

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_bfs(root):
    if not root:
        return []
    queue = deque([root])  # start with root in queue
    output = []
    while queue:
        node = queue.popleft()  # visit node at front of queue
        output.append(node.val)  # add node value to output
        if node.left:
            queue.append(node.left)  # enqueue left child
        if node.right:
            queue.append(node.right)  # enqueue right child
    return output

# Driver code to test
root = TreeNode(1)
root.left = TreeNode(2, TreeNode(4), TreeNode(5))
root.right = TreeNode(3, None, TreeNode(6))
result = level_order_bfs(root)
print(result)

queue = deque([root]) # start with root in queue

initialize queue with root node to begin level order traversal

while queue:

continue until all nodes are visited

node = queue.popleft() # visit node at front of queue

remove node from front to process current level nodes in order

output.append(node.val) # add node value to output

record visited node's value

if node.left: queue.append(node.left) # enqueue left child

add left child to queue for future visit

if node.right: queue.append(node.right) # enqueue right child

add right child to queue for future visit

Output

[1, 2, 3, 4, 5, 6]

Complexity Analysis

Time: O(n) because each node is visited exactly once

Space: O(n) because queue can hold up to all nodes at the widest level

vs Alternative: Compared to recursive depth-first traversals, BFS uses extra space for the queue but visits nodes level by level which is useful for shortest path or level-based problems

Edge Cases

Empty tree (root is None)

Returns empty list immediately

DSA Python

if not root:
    return []

Tree with only root node

Returns list with single root value

DSA Python

queue = deque([root])  # start with root in queue

Tree with missing children

Skips adding None children to queue, continues traversal

DSA Python

if node.left:
    queue.append(node.left)

When to Use This Pattern

When a problem asks to visit nodes level by level or find shortest path in a tree, use level order BFS because it processes nodes in layers from top to bottom.

Common Mistakes

Mistake: Forgetting to check if left or right child exists before adding to queue
Fix: Add conditionals to only enqueue non-null children

Mistake: Using stack or recursion which leads to depth-first order instead of level order
Fix: Use a queue data structure to maintain correct visiting order

Summary

Visits all nodes in a tree level by level from top to bottom.

Use when you need to process nodes in order of their distance from the root.

The key is to use a queue to keep track of nodes at the current level before moving deeper.

Practice

1. What does Level Order Traversal (BFS) of a binary tree do?

easy

A. Visits nodes in inorder (left, root, right)

B. Visits nodes level by level from top to bottom, left to right

C. Visits nodes in preorder (root, left, right)

D. Visits nodes in postorder (left, right, root)

Solution

1. Step 1: Understand Level Order Traversal

   Level order traversal visits nodes level by level starting from the root, moving left to right on each level.

2. Step 2: Compare with other traversals

   Preorder, inorder, and postorder traverse depth-first, not level by level.

3. Final Answer:

   Visits nodes level by level from top to bottom, left to right -> Option B

4. Quick Check:

   Level order = BFS = level by level [OK]

Hint: Level order means visiting nodes level by level [OK]

Common Mistakes:

• Confusing level order with preorder traversal
• Thinking level order is depth-first
• Mixing up left-to-right with right-to-left order

2. Which Python data structure is best suited to implement Level Order Traversal (BFS) of a binary tree?

easy

A. Stack

B. Dictionary

C. Set

D. Queue

Solution

1. Step 1: Identify traversal order needs

   Level order traversal requires visiting nodes in the order they appear level-wise, which is FIFO (first-in, first-out).

2. Step 2: Match data structure to FIFO

   A queue follows FIFO, so it is the best choice. Stack is LIFO, set and dictionary do not maintain order.

3. Final Answer:

   Queue -> Option D

4. Quick Check:

   Level order uses queue (FIFO) [OK]

Hint: Use queue for BFS to process nodes FIFO [OK]

Common Mistakes:

• Using stack instead of queue
• Using set which is unordered
• Using dictionary which is key-value, not order-based

3. What is the output of the following code for level order traversal?

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def level_order(root):
    if not root:
        return []
    result = []
    queue = [root]
    while queue:
        node = queue.pop(0)
        result.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return result

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print(level_order(root))

medium

A. [4, 5, 2, 3, 1]

B. [1, 3, 2, 5, 4]

C. [1, 2, 3, 4, 5]

D. [2, 4, 5, 1, 3]

Solution

1. Step 1: Trace the queue operations

   Start with queue = [1]. Pop 1, add 1 to result, enqueue 2 and 3. Queue = [2,3]. Pop 2, add 2, enqueue 4 and 5. Queue = [3,4,5]. Pop 3, add 3, no children. Queue = [4,5]. Pop 4, add 4. Queue = [5]. Pop 5, add 5. Queue empty.

2. Step 2: Collect the result list

   Result list after traversal is [1, 2, 3, 4, 5].

3. Final Answer:

   [1, 2, 3, 4, 5] -> Option C

4. Quick Check:

   Level order output matches [1, 2, 3, 4, 5] [OK]

Hint: Follow queue pops and appends step-by-step [OK]

Common Mistakes:

• Mixing left and right child order
• Using stack pop instead of queue pop
• Appending children in wrong order

4. Find the error in this level order traversal code:

def level_order(root):
    if root is None:
        return []
    queue = []
    result = []
    queue.append(root)
    while queue:
        node = queue.pop()
        result.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return result

medium

A. Using pop() removes last element, should use pop(0) for queue

B. Missing check if root is None

C. Appending children in wrong order

D. Result list is not initialized

Solution

1. Step 1: Identify queue operation mistake

   The code uses queue.pop() which removes the last element (LIFO), but BFS needs FIFO order, so pop(0) should be used.

2. Step 2: Understand impact on traversal order

   Using pop() makes traversal behave like DFS with stack, not BFS, so output will be incorrect.

3. Final Answer:

   Using pop() removes last element, should use pop(0) for queue -> Option A

4. Quick Check:

   pop(0) needed for BFS queue [OK]

Hint: Use pop(0) to dequeue from front in BFS [OK]

Common Mistakes:

• Using pop() instead of pop(0)
• Not initializing result list
• Appending children in wrong order

5. Given a binary tree, how can you modify level order traversal to return a list of lists, where each inner list contains nodes at that level? Choose the correct approach.

hard

A. Use a queue and track the number of nodes at each level, appending values level-wise

B. Use recursion to visit nodes in preorder and group by depth

C. Use a stack to store nodes and pop them level-wise

D. Traverse the tree inorder and split nodes by value ranges

Solution

1. Step 1: Understand level-wise grouping

   To group nodes by level, we can process nodes level by level using a queue and count how many nodes are at the current level.

2. Step 2: Implement counting and grouping

   At each iteration, record the size of the queue (number of nodes at current level), dequeue exactly that many nodes, collect their values, and enqueue their children for next level.

3. Final Answer:

   Use a queue and track the number of nodes at each level, appending values level-wise -> Option A

4. Quick Check:

   Queue + level count = grouped level order [OK]

Hint: Count nodes per level in queue to group them [OK]

Common Mistakes:

• Using recursion without tracking depth
• Using stack which is LIFO, not suitable
• Trying inorder traversal for level grouping