Tree Traversal Level Order BFS in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this level order traversal?

Given the binary tree below, what is the printed output of the level order traversal (BFS)?

Tree structure:
1
/ \
2 3
/ / \
4 5 6

DSA Python

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

def level_order(root):
    if not root:
        return []
    queue = [root]
    result = []
    while queue:
        node = queue.pop(0)
        result.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    print(' -> '.join(map(str, result)) + ' -> null')

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

level_order(root)

A 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

B 1 -> 3 -> 2 -> 6 -> 5 -> 4 -> null

C 4 -> 2 -> 5 -> 3 -> 6 -> 1 -> null

D 1 -> 2 -> 4 -> 3 -> 5 -> 6 -> null

💡 Hint

Remember, level order traversal visits nodes level by level from left to right.

Level order traversal visits nodes starting from the root, then all nodes at the next level from left to right, and so on. So the order is 1, then 2 and 3, then 4, 5, and 6.

❓ Predict Output

intermediate

Output of level order traversal with missing children

What is the output of the level order traversal for this tree?

Tree structure:
10
/ \
20 30
\ \
40 50

DSA Python

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

def level_order(root):
    if not root:
        return []
    queue = [root]
    result = []
    while queue:
        node = queue.pop(0)
        result.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    print(' -> '.join(map(str, result)) + ' -> null')

root = Node(10)
root.left = Node(20)
root.right = Node(30)
root.left.right = Node(40)
root.right.right = Node(50)

level_order(root)

A 10 -> 20 -> 30 -> 40 -> 50 -> null

B 10 -> 30 -> 20 -> 50 -> 40 -> null

C 10 -> 20 -> 40 -> 30 -> 50 -> null

D 10 -> 20 -> 30 -> 50 -> 40 -> null

💡 Hint

Check the order nodes are added to the queue: left child first, then right child.

Level order visits root first (10), then its children left to right (20, 30), then their children (40 from 20's right, 50 from 30's right).

🔧 Debug

advanced

Identify the error in this level order traversal code

What error does this code raise when run on a non-empty tree?

DSA Python

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

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)
    print(' -> '.join(map(str, result)) + ' -> null')

A No error, prints correct level order

B IndexError due to popping from empty list

C The output is reversed level order traversal

D TypeError due to wrong data type in queue

💡 Hint

Check how elements are removed from the queue.

Using pop() without index removes the last element, making the traversal depth-first (stack behavior), reversing the order of nodes visited compared to BFS.

🧠 Conceptual

advanced

What is the time complexity of level order traversal?

Given a binary tree with n nodes, what is the time complexity of performing a level order traversal?

A O(n^2)

B O(n)

C O(n log n)

D O(log n)

💡 Hint

Each node is visited exactly once.

Level order traversal visits each node once and processes it in constant time, so total time is proportional to number of nodes, O(n).

🚀 Application

expert

Find the maximum value at each level using level order traversal

Given a binary tree, which code snippet correctly prints the maximum value at each level using level order traversal?

A

def max_per_level(root):
    if not root:
        return []
    queue = [root]
    max_val = float('-inf')
    while queue:
        node = queue.pop(0)
        if node.val > max_val:
            max_val = node.val
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    print(max_val)

B

def max_per_level(root):
    if not root:
        return []
    queue = [root]
    while queue:
        level_size = len(queue)
        max_val = float('-inf')
        for i in range(level_size):
            node = queue.pop()
            if node.val > max_val:
                max_val = node.val
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        print(max_val)

C

def max_per_level(root):
    if not root:
        return []
    queue = [root]
    while queue:
        max_val = float('-inf')
        node = queue.pop(0)
        if node.val > max_val:
            max_val = node.val
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
        print(max_val)

D

def max_per_level(root):
    if not root:
        return []
    queue = [root]
    while queue:
        level_size = len(queue)
        max_val = float('-inf')
        for _ in range(level_size):
            node = queue.pop(0)
            if node.val > max_val:
                max_val = node.val
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        print(max_val)

💡 Hint

Remember to process all nodes at the current level before printing max.

Option D correctly processes nodes level by level using a for loop over level_size, updates max_val per level, and prints after each level. Others either do not separate levels or pop from wrong end.

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