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.

Practice

1. What does the "maximum width" of a binary tree represent?

easy

A. The sum of values of all nodes at the widest level

B. The height of the tree from root to the deepest leaf

C. The total number of nodes in the tree

D. The largest number of nodes present at any single level of the tree

Solution

1. Step 1: Understand the definition of width in a binary tree

   The width is the count of nodes at a particular level in the tree.

2. Step 2: Identify maximum width

   The maximum width is the largest such count among all levels.

3. Final Answer:

   The largest number of nodes present at any single level of the tree -> Option D

4. Quick Check:

   Maximum width = max nodes at any level [OK]

Hint: Width means count of nodes at one level, not height or sum [OK]

Common Mistakes:

• Confusing width with height of the tree
• Thinking width is sum of node values
• Counting total nodes instead of per level

2. Which Go data structure is best suited to track nodes level by level when finding maximum width of a binary tree?

easy

A. Queue

B. Stack

C. Map

D. Slice

Solution

1. Step 1: Identify traversal method for level order

   Level order traversal requires processing nodes level by level, which is done using a queue.

2. Step 2: Choose data structure

   A queue allows nodes to be added at the end and removed from the front, perfect for breadth-first traversal.

3. Final Answer:

   Queue -> Option A

4. Quick Check:

   Level order traversal uses queue [OK]

Hint: Use queue for level order traversal to measure width [OK]

Common Mistakes:

• Using stack which is LIFO, not suitable for level order
• Using map which doesn't preserve order
• Using slice without queue operations

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

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

func maxWidth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    queue := []*TreeNode{root}
    maxWidth := 0
    for len(queue) > 0 {
        levelSize := len(queue)
        if levelSize > maxWidth {
            maxWidth = 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 maxWidth
}

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(maxWidth(root))

medium

A. 3

B. 2

C. 4

D. 5

Solution

1. Step 1: Analyze tree structure and levels

   Level 1: Node 1 (1 node), Level 2: Nodes 2 and 3 (2 nodes), Level 3: Nodes 4 and 5 (2 nodes)

2. Step 2: Calculate maximum width

   Maximum width is the largest number of nodes at any level, which is 2.

3. Step 3: Re-examine the tree structure carefully

   Actually, at Level 3, nodes are 4 and 5 (2 nodes), but at Level 2, nodes are 2 and 3 (2 nodes), so max width is 2. However, the code counts the queue size before processing children, so at Level 1 queue size is 1, Level 2 queue size is 2, Level 3 queue size is 2. The maximum width is 2.

4. Step 4: Check if any level has 3 nodes

   No level has 3 nodes, so 3 (3) is incorrect.

5. Final Answer:

   2 -> Option B

6. Quick Check:

   Max nodes at any level = 2 [OK]

Hint: Count nodes per level carefully to find max width [OK]

Common Mistakes:

• Counting total nodes instead of per level
• Miscounting nodes at last level
• Assuming root level has more nodes

4. Identify the bug in this Go code snippet that attempts to find the maximum width of a binary tree:

func maxWidth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    queue := []*TreeNode{root}
    maxWidth := 0
    for len(queue) > 0 {
        levelSize := len(queue)
        if levelSize > maxWidth {
            maxWidth = 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 maxWidth
}

medium

A. The inner loop condition should be i < levelSize, not i <= levelSize

B. The queue should be initialized empty, not with root

C. The maxWidth should be updated after the inner loop

D. The function should return maxWidth + 1

Solution

1. Step 1: Check loop boundaries for processing nodes

   The inner loop runs from i = 0 to i <= levelSize, which means it runs levelSize + 1 times, causing out-of-range error.

2. Step 2: Correct loop condition

   The loop should run exactly levelSize times, so condition must be i < levelSize.

3. Final Answer:

   The inner loop condition should be i < levelSize, not i <= levelSize -> Option A

4. Quick Check:

   Loop runs one extra time causing error [OK]

Hint: Use < for loops when iterating fixed count [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Initializing queue incorrectly
• Updating maxWidth at wrong time

5. Given a binary tree where some nodes are missing children, how can you modify the maximum width calculation to include the 'null' positions between nodes, effectively measuring the width as the distance between the leftmost and rightmost non-null nodes at each level? Choose the best approach to implement this in Go.

hard

A. Use recursion to count nodes and ignore null gaps

B. Count only non-null nodes per level ignoring positions

C. Use a queue storing pairs of (node, index) where index represents position, and calculate width as max index difference per level

D. Calculate width as total nodes in tree divided by height

Solution

1. Step 1: Understand the problem of null gaps

   Normal width counts nodes only, but to include gaps, we track positions of nodes as if tree was complete.

2. Step 2: Use index tracking with queue

   Store each node with an index representing its position. For each level, width = last index - first index + 1.

3. Step 3: Implement with queue of (node, index) pairs

   This approach allows measuring width including null gaps between nodes.

4. Final Answer:

   Use a queue storing pairs of (node, index) where index represents position, and calculate width as max index difference per level -> Option C

5. Quick Check:

   Index tracking captures null gaps in width [OK]

Hint: Track node positions with indices to include gaps [OK]

Common Mistakes:

• Ignoring null gaps by counting only nodes
• Using recursion without position tracking
• Calculating width as total nodes divided by height