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.