Tree Traversal Level Order BFS in DSA Python - Execution Trace

Concept Flow - Tree Traversal Level Order BFS

Start at root node

↓

Add root to queue

↓

While queue not empty

↓

Remove node from front of queue

↓

Visit node (process value)

↓

Add left child to queue if exists

↓

Add right child to queue if exists

↓

Repeat loop until queue empty

↓

Traversal complete

Start from the root, use a queue to visit nodes level by level, adding children to the queue as you go.

Execution Sample

DSA Python

from collections import deque

def level_order_bfs(root):
    if not root:
        return []
    queue = deque([root])
    result = []
    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

This code visits each node of a binary tree level by level using a queue and collects their values.

Execution Table

Step	Operation	Queue Content (Node Values)	Visited Nodes	Visual Tree State
1	Start with root node 1	[1]	[]	1 / \ 2 3 / \ \ 4 5 6
2	Pop 1, visit it	[]	[1]	1* / \ 2 3 / \ \ 4 5 6
3	Add children 2 and 3 to queue	[2, 3]	[1]	1* / \ 2 3 / \ \ 4 5 6
4	Pop 2, visit it	[3]	[1, 2]	1* / \ 2* 3 / \ \ 4 5 6
5	Add children 4 and 5 to queue	[3, 4, 5]	[1, 2]	1* / \ 2* 3 / \ \ 4 5 6
6	Pop 3, visit it	[4, 5]	[1, 2, 3]	1* / \ 2* 3* / \ \ 4 5 6
7	Add child 6 to queue	[4, 5, 6]	[1, 2, 3]	1* / \ 2* 3* / \ \ 4 5 6
8	Pop 4, visit it	[5, 6]	[1, 2, 3, 4]	1* / \ 2* 3* / \ \ 4* 5 6
9	4 has no children, queue unchanged	[5, 6]	[1, 2, 3, 4]	1* / \ 2* 3* / \ \ 4* 5 6
10	Pop 5, visit it	[6]	[1, 2, 3, 4, 5]	1* / \ 2* 3* / \ \ 4* 5* 6
11	5 has no children, queue unchanged	[6]	[1, 2, 3, 4, 5]	1* / \ 2* 3* / \ \ 4* 5* 6
12	Pop 6, visit it	[]	[1, 2, 3, 4, 5, 6]	1* / \ 2* 3* / \ \ 4* 5* 6*
13	6 has no children, queue empty	[]	[1, 2, 3, 4, 5, 6]	Traversal complete

💡 Queue is empty, all nodes visited

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 8	After Step 10	After Step 12	Final
queue	[1]	[2, 3]	[3, 4, 5]	[4, 5, 6]	[5, 6]	[6]	[]	[]
visited	[]	[1]	[1, 2]	[1, 2, 3]	[1, 2, 3, 4]	[1, 2, 3, 4, 5]	[1, 2, 3, 4, 5, 6]	[1, 2, 3, 4, 5, 6]

Key Moments - 3 Insights

Why do we add children to the queue after visiting a node?

Because BFS visits nodes level by level, adding children to the queue ensures nodes on the next level are visited after current level nodes, as shown in steps 3, 5, and 7 in the execution_table.

Why does the queue start with only the root node?

The traversal begins at the root, so we add only the root to the queue initially (step 1). This sets the starting point for visiting all nodes.

What happens when a node has no children?

No new nodes are added to the queue, so the queue size decreases as nodes are popped, shown in steps 9, 11, and 13 where nodes 4, 5, and 6 have no children.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the queue content?

A [4, 5, 6]

B [2, 3]

C [3, 4, 5]

D [5, 6]

💡 Hint

Check the 'Queue Content (Node Values)' column at step 6 in the execution_table.

At which step does the queue become empty?

A Step 10

B Step 12

C Step 13

D Step 9

💡 Hint

Look at the 'Queue Content' column and find when it shows [].

If node 3 had no right child, how would the queue change after step 6?

A Queue would be [3, 4, 5]

B Queue would be [4, 5]

C Queue would be [4, 5, 6]

D Queue would be [5, 6]

💡 Hint

Refer to step 7 where children of node 3 are added to the queue.

Concept Snapshot

Level Order BFS Traversal:
- Use a queue starting with root node
- While queue not empty:
  - Pop front node, visit it
  - Add left child if exists
  - Add right child if exists
- Visits nodes level by level
- Result is nodes in order of levels

Full Transcript

Level Order BFS traversal visits nodes of a binary tree level by level using a queue. It starts by adding the root node to the queue. Then, while the queue is not empty, it removes the front node, visits it, and adds its children to the queue if they exist. This process continues until all nodes are visited and the queue is empty. The execution table shows each step with the queue content, visited nodes, and the visual state of the tree. Key moments clarify why children are added after visiting nodes, why the queue starts with the root, and what happens when nodes have no children. The visual quiz tests understanding of queue content at specific steps and effects of missing children.

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