Zigzag Level Order Traversal in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Zigzag Level Order Traversal on a Binary Tree

What is the output of the zigzag level order traversal for the given binary tree?

DSA Go

package main

import "fmt"

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

func zigzagLevelOrder(root *TreeNode) [][]int {
    if root == nil {
        return [][]int{}
    }
    var result [][]int
    var currentLevel []*TreeNode
    currentLevel = append(currentLevel, root)
    leftToRight := true

    for len(currentLevel) > 0 {
        var levelVals []int
        var nextLevel []*TreeNode

        for _, node := range currentLevel {
            levelVals = append(levelVals, node.Val)
        }

        if !leftToRight {
            for i, j := 0, len(levelVals)-1; i < j; i, j = i+1, j-1 {
                levelVals[i], levelVals[j] = levelVals[j], levelVals[i]
            }
        }

        for _, node := range currentLevel {
            if node.Left != nil {
                nextLevel = append(nextLevel, node.Left)
            }
            if node.Right != nil {
                nextLevel = append(nextLevel, node.Right)
            }
        }

        result = append(result, levelVals)
        currentLevel = nextLevel
        leftToRight = !leftToRight
    }

    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}
    root.Right.Right = &TreeNode{Val: 6}

    result := zigzagLevelOrder(root)
    fmt.Println(result)
}

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

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

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

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

💡 Hint

Remember that zigzag means alternating the order of nodes at each level.

The traversal starts left to right at level 0, so [1]. Then it goes right to left at level 1, so [3, 2]. Finally, it goes left to right at level 2, so [4, 5, 6].

🧠 Conceptual

intermediate

Understanding Zigzag Level Order Traversal Direction

In zigzag level order traversal, what determines the order of nodes at each level?

A The level number: even levels left to right, odd levels right to left

B The number of children a node has

C The value of the node: even values left to right, odd values right to left

D The height of the tree

💡 Hint

Think about how the traversal direction changes as you go down levels.

Zigzag traversal alternates direction by level number: even levels are traversed left to right, odd levels right to left.

🔧 Debug

advanced

Identify the Bug in Zigzag Traversal Code

What error will this code produce when run, and why? func zigzagLevelOrder(root *TreeNode) [][]int { if root == nil { return [][]int{} } var result [][]int var currentLevel []*TreeNode currentLevel = append(currentLevel, root) leftToRight := true for len(currentLevel) > 0 { var levelVals []int var nextLevel []*TreeNode for i := len(currentLevel) - 1; i >= 0; i-- { node := currentLevel[i] levelVals = append(levelVals, node.Val) if leftToRight { if node.Left != nil { nextLevel = append(nextLevel, node.Left) } if node.Right != nil { nextLevel = append(nextLevel, node.Right) } } else { if node.Right != nil { nextLevel = append(nextLevel, node.Right) } if node.Left != nil { nextLevel = append(nextLevel, node.Left) } } } result = append(result, levelVals) currentLevel = nextLevel leftToRight = !leftToRight } return result }

A The code will panic due to nil pointer dereference

B The code will cause an infinite loop

C The code will run correctly and produce the expected zigzag output

D The traversal order of nodes in nextLevel is incorrect, causing wrong zigzag output

💡 Hint

Check how nextLevel nodes are added and in what order.

The order of adding children to nextLevel is wrong because appending in this order while iterating backwards causes the next level to be in incorrect order, breaking the zigzag pattern.

🚀 Application

advanced

Number of Levels in Zigzag Traversal Output

Given a binary tree with 7 nodes arranged as a complete binary tree of height 3, how many levels will the zigzag level order traversal output contain?

A 3

B 7

C 4

D 2

💡 Hint

Think about how many levels a complete binary tree of height 3 has.

A complete binary tree of height 3 has exactly 3 levels, so the traversal output will have 3 lists.

❓ Predict Output

expert

Output of Zigzag Traversal on Unbalanced Tree

What is the output of the zigzag level order traversal for this unbalanced binary tree? Tree structure: - Root: 10 - Root.Left: 5 - Root.Left.Left: 3 - Root.Left.Left.Left: 1 - Root.Right: 15 - Root.Right.Right: 20

DSA Go

package main

import "fmt"

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

func zigzagLevelOrder(root *TreeNode) [][]int {
    if root == nil {
        return [][]int{}
    }
    var result [][]int
    var currentLevel []*TreeNode
    currentLevel = append(currentLevel, root)
    leftToRight := true

    for len(currentLevel) > 0 {
        var levelVals []int
        var nextLevel []*TreeNode

        for _, node := range currentLevel {
            levelVals = append(levelVals, node.Val)
        }

        if !leftToRight {
            for i, j := 0, len(levelVals)-1; i < j; i, j = i+1, j-1 {
                levelVals[i], levelVals[j] = levelVals[j], levelVals[i]
            }
        }

        for _, node := range currentLevel {
            if node.Left != nil {
                nextLevel = append(nextLevel, node.Left)
            }
            if node.Right != nil {
                nextLevel = append(nextLevel, node.Right)
            }
        }

        result = append(result, levelVals)
        currentLevel = nextLevel
        leftToRight = !leftToRight
    }

    return result
}

func main() {
    root := &TreeNode{Val: 10}
    root.Left = &TreeNode{Val: 5}
    root.Left.Left = &TreeNode{Val: 3}
    root.Left.Left.Left = &TreeNode{Val: 1}
    root.Right = &TreeNode{Val: 15}
    root.Right.Right = &TreeNode{Val: 20}

    result := zigzagLevelOrder(root)
    fmt.Println(result)
}

A [[10], [15, 5], [20, 3], [1]]

B [[10], [5, 15], [3, 20], [1]]

C [[10], [15, 5], [3, 20], [1]]

D [[10], [5, 15], [20, 3], [1]]

💡 Hint

Remember to alternate the order of nodes at each level, even if the tree is unbalanced.

The traversal starts left to right at level 0: [10]. Then right to left at level 1: [15, 5]. Then left to right at level 2: [3, 20]. Finally right to left at level 3: [1].