Tree Traversal Level Order BFS in DSA Python - Build from Scratch

Tree Traversal Level Order BFS

📖 Scenario: Imagine you have a family tree and you want to visit each generation one by one, starting from the oldest ancestor down to the youngest children. This is like visiting nodes level by level in a tree.

🎯 Goal: You will build a program that performs a level order traversal (Breadth-First Search) on a simple binary tree and prints the nodes level by level.

📋 What You'll Learn

Create a binary tree using a Node class with value, left, and right attributes

Create a queue to help with the level order traversal

Implement the level order traversal using a while loop and queue operations

Print the values of nodes in level order separated by spaces

💡 Why This Matters

🌍 Real World

Level order traversal is used in many real-world problems like finding the shortest path in maps, scheduling tasks, and organizing hierarchical data.

💼 Career

Understanding BFS and tree traversal is essential for software engineers working with data structures, algorithms, and system design.

1

Create the binary tree nodes

Create a class called Node with an __init__ method that takes value, left, and right parameters. Then create the root node called root with value 1, left child with value 2, and right child with value 3. The left child of root should have a left child with value 4 and right child with value 5. The right child of root should have no children.

DSA Python

# Define the Node class and create the tree nodes
# Your code here

Hint

Remember, each node can have a left and right child. Use None if there is no child.

2

Set up the queue for BFS

Create a list called queue and initialize it with the root node inside it. This queue will help us visit nodes level by level.

DSA Python

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

root = Node(1,
            Node(2,
                 Node(4),
                 Node(5)),
            Node(3))

# Create a queue list with root node
# Your code here

Hint

Use a list with the root node inside square brackets to start the queue.

3

Implement the level order traversal logic

Use a while loop that runs as long as queue is not empty. Inside the loop, remove the first node from queue using pop(0) and store it in current. Print the current.value followed by a space (use end=' '). If current.left exists, add it to the end of queue. If current.right exists, add it to the end of queue.

DSA Python

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

root = Node(1,
            Node(2,
                 Node(4),
                 Node(5)),
            Node(3))

queue = [root]

# Write the while loop for level order traversal
# Your code here

Hint

Use pop(0) to get the first node and append() to add children to the queue.

4

Print the final output

Run the program to print the values of the nodes in level order separated by spaces.

DSA Python

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

root = Node(1,
            Node(2,
                 Node(4),
                 Node(5)),
            Node(3))

queue = [root]

while queue:
    current = queue.pop(0)
    print(current.value, end=' ')
    if current.left:
        queue.append(current.left)
    if current.right:
        queue.append(current.right)

# Run the program to see the output

Hint

The output should show the nodes visited level by level: 1 2 3 4 5

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