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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Level Order Traversal on a Simple Tree

What is the output of the following Go code performing level order traversal (BFS) on a binary tree?

DSA Go

package main

import "fmt"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func levelOrder(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }
    queue := []*TreeNode{root}
    result := []int{}
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        result = append(result, node.Val)
        if node.Left != nil {
            queue = append(queue, node.Left)
        }
        if node.Right != nil {
            queue = append(queue, node.Right)
        }
    }
    return result
}

func main() {
    root := &TreeNode{Val: 1}
    root.Left = &TreeNode{Val: 2}
    root.Right = &TreeNode{Val: 3}
    root.Left.Left = &TreeNode{Val: 4}
    root.Left.Right = &TreeNode{Val: 5}
    fmt.Println(levelOrder(root))
}

A [1 2 3 4 5]

B [1 3 2 4 5]

C [4 5 2 3 1]

D [1 2 4 5 3]

💡 Hint

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

The traversal visits root first (1), then its children (2, 3), then the next level children (4, 5). So the output is [1 2 3 4 5].

🧠 Conceptual

intermediate

Understanding Queue Usage in Level Order Traversal

Why is a queue used in level order traversal (BFS) of a binary tree instead of a stack?

A Because a queue uses less memory than a stack.

B Because a stack processes nodes in FIFO order, which is needed for BFS.

C Because a queue processes nodes in FIFO order, preserving the level order sequence.

D Because a stack cannot store tree nodes.

💡 Hint

Think about the order nodes are visited in BFS.

A queue processes nodes in the order they were added (first-in, first-out), which matches the level order traversal visiting nodes level by level. A stack uses last-in, first-out order, which is not suitable for BFS.

🔧 Debug

advanced

Identify the Bug in Level Order Traversal Code

What error will the following Go code produce when performing level order traversal?

DSA Go

func levelOrder(root *TreeNode) []int {
    var queue []*TreeNode
    var result []int
    queue = append(queue, root)
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        result = append(result, node.Val)
        if node.Left != nil {
            queue = append(queue, node.Left)
        }
        if node.Right != nil {
            queue = append(queue, node.Right)
        }
    }
    return result
}

A No error, outputs correct traversal

B SyntaxError: missing return statement

C IndexError: slice index out of range

D runtime error: invalid memory address or nil pointer dereference

💡 Hint

What happens if root is nil?

If root is nil, it is appended to the queue. Then node.Val causes a nil pointer dereference runtime error.

❓ Predict Output

advanced

Output of Level Order Traversal with Unbalanced Tree

What is the output of the following Go code performing level order traversal on an unbalanced binary tree?

DSA Go

package main

import "fmt"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func levelOrder(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }
    queue := []*TreeNode{root}
    result := []int{}
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        result = append(result, node.Val)
        if node.Left != nil {
            queue = append(queue, node.Left)
        }
        if node.Right != nil {
            queue = append(queue, node.Right)
        }
    }
    return result
}

func main() {
    root := &TreeNode{Val: 10}
    root.Right = &TreeNode{Val: 20}
    root.Right.Right = &TreeNode{Val: 30}
    fmt.Println(levelOrder(root))
}

A [10 30 20]

B [10 20 30]

C [30 20 10]

D [10 20]

💡 Hint

Level order visits nodes level by level, left to right.

The tree has nodes 10 at root, 20 as right child, and 30 as right child of 20. The traversal visits 10, then 20, then 30.

🚀 Application

expert

Number of Nodes at Each Level Using Level Order Traversal

Given a binary tree, which code snippet correctly returns a slice of integers representing the count of nodes at each level using level order traversal in Go?

A

func countNodesPerLevel(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }
    queue := []*TreeNode{root}
    counts := []int{}
    for len(queue) > 0 {
        levelSize := len(queue)
        counts = append(counts, levelSize)
        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
    }
    return counts
}

B

func countNodesPerLevel(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }
    queue := []*TreeNode{root}
    counts := []int{}
    for len(queue) > 0 {
        levelSize := len(queue)
        counts = append(counts, levelSize)
        for i := 0; i <= levelSize; i++ {
            node := queue[0]
            queue = queue[1:]
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
    }
    return counts
}

C

func countNodesPerLevel(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }
    queue := []*TreeNode{root}
    counts := []int{}
    for len(queue) > 0 {
        levelSize := len(queue)
        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        counts = append(counts, levelSize)
    }
    return counts
}

D

func countNodesPerLevel(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }
    queue := []*TreeNode{root}
    counts := []int{}
    for len(queue) > 0 {
        counts = append(counts, len(queue))
        node := queue[0]
        queue = queue[1:]
        if node.Left != nil {
            queue = append(queue, node.Left)
        }
        if node.Right != nil {
            queue = append(queue, node.Right)
        }
    }
    return counts
}

💡 Hint

Count nodes before processing each level, and process exactly that many nodes per level.

Option A correctly counts nodes per level by recording the queue length before processing that level's nodes. Other options either count incorrectly or have off-by-one errors.

Practice

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

easy

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

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

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

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

Solution

1. Step 1: Understand Level Order Traversal

   Level order traversal visits nodes one level at a time, starting from the root and moving down each level from left to right.

2. Step 2: Compare with other traversals

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

3. Final Answer:

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

4. Quick Check:

   Level order = BFS = level by level [OK]

Hint: Level order means visit nodes by levels, top to bottom [OK]

Common Mistakes:

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

2. Which Go code snippet correctly initializes a queue for BFS traversal of a binary tree?

easy

A. queue := make(TreeNode)

B. queue := []*TreeNode{}

C. queue := TreeNode{}

D. queue := []TreeNode

Solution

1. Step 1: Identify correct queue initialization

   In Go, a queue for BFS is usually a slice of pointers to TreeNode, so []*TreeNode{} initializes an empty slice correctly.

2. Step 2: Check other options

   make(TreeNode) is invalid because make is for slices, maps, channels, not structs. TreeNode{} is a struct instance, not a queue. []TreeNode is a slice type declaration missing initialization.

3. Final Answer:

   queue := []*TreeNode{} -> Option B

4. Quick Check:

   Queue for BFS = slice of *TreeNode [OK]

Hint: Use slice of pointers []*TreeNode{} for BFS queue [OK]

Common Mistakes:

• Using make with struct type instead of slice
• Declaring slice type without initialization
• Using struct instance instead of slice

3. What is the output of the following Go code performing level order traversal on this tree?

type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}

func levelOrder(root *TreeNode) []int {
  if root == nil {
    return []int{}
  }
  queue := []*TreeNode{root}
  result := []int{}
  for len(queue) > 0 {
    node := queue[0]
    queue = queue[1:]
    result = append(result, node.Val)
    if node.Left != nil {
      queue = append(queue, node.Left)
    }
    if node.Right != nil {
      queue = append(queue, node.Right)
    }
  }
  return result
}

root := &TreeNode{Val: 1}
root.Left = &TreeNode{Val: 2}
root.Right = &TreeNode{Val: 3}
root.Left.Left = &TreeNode{Val: 4}
root.Left.Right = &TreeNode{Val: 5}

fmt.Println(levelOrder(root))

medium

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

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

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

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

Solution

1. Step 1: Trace the BFS queue processing

   Start with queue=[1]. Visit 1, enqueue 2 and 3. Queue=[2,3]. Visit 2, enqueue 4 and 5. Queue=[3,4,5]. Visit 3 (no children). Queue=[4,5]. Visit 4 (no children). Queue=[5]. Visit 5 (no children). Queue empty.

2. Step 2: Collect visited nodes in order

   Visited nodes in order: 1, 2, 3, 4, 5.

3. Final Answer:

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

4. Quick Check:

   BFS visits nodes level-wise: 1,2,3,4,5 [OK]

Hint: Follow queue order: enqueue children left then right [OK]

Common Mistakes:

• Visiting right child before left child
• Confusing BFS with DFS order
• Forgetting to append children to queue

4. The following Go code for level order traversal has a bug. What is the error?

func levelOrder(root *TreeNode) []int {
  if root == nil {
    return []int{}
  }
  queue := []*TreeNode{root}
  result := []int{}
  for len(queue) > 0 {
    node := queue[0]
    // Missing queue update here
    result = append(result, node.Val)
    if node.Left != nil {
      queue = append(queue, node.Left)
    }
    if node.Right != nil {
      queue = append(queue, node.Right)
    }
  }
  return result
}

medium

A. The root node is never added to the queue

B. Children nodes are not appended to the queue

C. The queue is never shortened, causing an infinite loop

D. The result slice is not initialized

Solution

1. Step 1: Identify queue update in BFS loop

   In BFS, after processing the first node, it must be removed from the queue (queue = queue[1:]). This code misses that step.

2. Step 2: Consequence of missing queue update

   Without removing the first node, the queue length never decreases, causing an infinite loop.

3. Final Answer:

   The queue is never shortened, causing an infinite loop -> Option C

4. Quick Check:

   Queue must shrink each iteration [OK]

Hint: Always remove processed node from queue in BFS loop [OK]

Common Mistakes:

• Forgetting to dequeue the current node
• Appending children incorrectly
• Not initializing result slice

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 only? Which approach is correct in Go? A) Use a queue and track the number of nodes at current level, dequeue exactly that many nodes, then enqueue their children. B) Use recursion to visit nodes and append values to a global list. C) Use a stack instead of a queue to reverse the order. D) Traverse the tree inorder and group nodes by their depth using a map.

hard

A. Use a queue and track nodes count per level, process level by level

B. Use recursion and append nodes to a single list

C. Use a stack to reverse traversal order

D. Use inorder traversal and group nodes by depth in a map

Solution

1. Step 1: Understand level grouping in BFS

   To group nodes by level, track how many nodes are at the current level (queue length before processing), then dequeue exactly that many nodes and collect their values.

2. Step 2: Why other options are incorrect

   Recursion without level tracking won't separate levels. Stack reverses order but doesn't group levels. Inorder traversal visits nodes depth-first, not level-wise, so grouping by depth is complex and not BFS.

3. Final Answer:

   Use a queue and track nodes count per level, process level by level -> Option A

4. Quick Check:

   Level order + count nodes per level = grouped levels [OK]

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

Common Mistakes:

• Using recursion without level tracking
• Using stack instead of queue for BFS
• Trying inorder traversal for level grouping