Tree Traversal Level Order BFS in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the queue with the root node for level order traversal.

DSA Python

queue = [[1]]

Drag options to blanks, or click blank then click option'

ANone

Broot

C[]

Dqueue

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing queue as empty list instead of with root.

Using None instead of root.

We start the level order traversal by putting the root node into the queue.

2fill in blank

medium

Complete the code to remove the first node from the queue during traversal.

DSA Python

current = queue.[1]()

Drag options to blanks, or click blank then click option'

Apop

Bremove

Cpop(0)

Dpopitem

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop() which removes from the end.

Using remove() which removes by value.

We remove the first element from the queue using pop(0) to follow FIFO order.

3fill in blank

hard

Fix the error in adding the left child to the queue only if it exists.

DSA Python

if current.left [1] None:
    queue.append(current.left)

Drag options to blanks, or click blank then click option'

Ais not

B!=

Cis

D==

Attempts:

3 left

💡 Hint

Common Mistakes

Using '==' None which is less preferred.

Using '!=' None which works but 'is not' is clearer.

We check if current.left is not None before adding it to the queue.

4fill in blank

hard

Fill both blanks to correctly add the right child to the queue if it exists.

DSA Python

if current.[1] [2] None:
    queue.append(current.right)

Drag options to blanks, or click blank then click option'

Aright

Bleft

Cis not

Dis

Attempts:

3 left

💡 Hint

Common Mistakes

Checking left child instead of right.

Using 'is' instead of 'is not' causing wrong condition.

Check if current.right is not None before appending it to the queue.

5fill in blank

hard

Fill all three blanks to complete the level order traversal loop that collects node values.

DSA Python

result = []
queue = [root]
while queue:
    current = queue.pop(0)
    result.append(current.[1])
    if current.left [2] None:
        queue.append(current.left)
    if current.right [3] None:
        queue.append(current.right)

Drag options to blanks, or click blank then click option'

Aval

Bis not

Cis

Dvalue

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong attribute name for node value.

Using 'is' instead of 'is not' causing children to be skipped.

We append the node's value, and add left and right children if they exist (not None).

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