Maximum Width of Binary Tree in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Maximum Width Calculation for a Simple Tree

What is the output of the following Go code that calculates the maximum width of a binary tree?

DSA Go

package main

import "fmt"

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

func widthOfBinaryTree(root *TreeNode) int {
    if root == nil {
        return 0
    }
    maxWidth := 0
    queue := []struct {
        node  *TreeNode
        index int
    }{{root, 0}}

    for len(queue) > 0 {
        levelLength := len(queue)
        startIndex := queue[0].index
        endIndex := queue[levelLength-1].index
        if endIndex-startIndex+1 > maxWidth {
            maxWidth = endIndex - startIndex + 1
        }
        newQueue := []struct {
            node  *TreeNode
            index int
        }{}
        for i := 0; i < levelLength; i++ {
            current := queue[i]
            if current.node.Left != nil {
                newQueue = append(newQueue, struct {
                    node  *TreeNode
                    index int
                }{current.node.Left, 2*(current.index - startIndex) + 1})
            }
            if current.node.Right != nil {
                newQueue = append(newQueue, struct {
                    node  *TreeNode
                    index int
                }{current.node.Right, 2*(current.index - startIndex) + 2})
            }
        }
        queue = newQueue
    }
    return maxWidth
}

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

A 5

B 4

C 3

D 2

💡 Hint

Consider how the width is calculated including null positions between nodes.

The maximum width is calculated by considering the position indices of nodes at each level. Here, the widest level is the last one with nodes 4 and 5 at positions 0 and 3 respectively, so width = 3 - 0 + 1 = 4.

🧠 Conceptual

intermediate

Understanding Indexing in Maximum Width Calculation

In the maximum width calculation of a binary tree, why do we subtract the start index from each node's index before calculating the child indices?

A To ensure the indices start from zero at each level for accurate width calculation

B To skip null nodes in the tree and only count existing nodes

C To prevent integer overflow by normalizing indices at each level

D To double the indices for left and right children

💡 Hint

Think about how large index values can grow in a deep tree.

Subtracting the start index at each level normalizes indices to prevent integer overflow and keeps the indices manageable while preserving relative positions for width calculation.

🔧 Debug

advanced

Identify the Error in Width Calculation Code

What error will the following Go code produce when calculating the maximum width of a binary tree?

DSA Go

func widthOfBinaryTree(root *TreeNode) int {
    if root == nil {
        return 0
    }
    maxWidth := 0
    queue := []struct {
        node  *TreeNode
        index int
    }{{root, 1}}

    for len(queue) > 0 {
        levelLength := len(queue)
        startIndex := queue[0].index
        endIndex := queue[levelLength-1].index
        if endIndex-startIndex+1 > maxWidth {
            maxWidth = endIndex - startIndex + 1
        }
        newQueue := []struct {
            node  *TreeNode
            index int
        }{}
        for i := 0; i < levelLength; i++ {
            current := queue[i]
            if current.node.Left != nil {
                newQueue = append(newQueue, struct {
                    node  *TreeNode
                    index int
                }{current.node.Left, 2*current.index})
            }
            if current.node.Right != nil {
                newQueue = append(newQueue, struct {
                    node  *TreeNode
                    index int
                }{current.node.Right, 2*current.index + 1})
            }
        }
        queue = newQueue
    }
    return maxWidth
}

A The width calculation will be incorrect because indices are not normalized per level

B The code will panic due to integer overflow on large trees

C The code will not compile due to missing import statements

D The code will return zero for all trees

💡 Hint

Check how indices are assigned to child nodes and how they relate to the start index of the level.

The code does not normalize indices by subtracting the start index at each level, so indices can grow large and cause incorrect width calculations.

🚀 Application

advanced

Maximum Width of a Sparse Binary Tree

Given a binary tree where some nodes are missing, what is the maximum width of the tree after running the width calculation algorithm?

DSA Go

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

A 4

B 3

C 6

D 5

💡 Hint

Consider the positions of nodes including gaps caused by missing nodes.

The maximum width is the largest distance between the leftmost and rightmost nodes at any level, counting null positions. Here, the widest level includes nodes at positions 0 and 4, so width = 5.

🧠 Conceptual

expert

Why Use BFS with Indexing for Maximum Width?

Why is breadth-first search (BFS) combined with indexing nodes important for calculating the maximum width of a binary tree?

A BFS visits nodes level by level and indexing tracks positions to measure width including gaps

B BFS is faster than depth-first search (DFS) for all tree operations

C Indexing nodes allows skipping null nodes to reduce memory usage

D BFS with indexing avoids recursion and stack overflow errors

💡 Hint

Think about how width is defined and how BFS helps measure it.

BFS visits nodes level by level, which is necessary to measure width at each level. Indexing nodes tracks their positions including gaps caused by missing nodes, allowing accurate width calculation.