Maximum Width of Binary Tree in DSA Go - Build from Scratch

Maximum Width of Binary Tree

📖 Scenario: You are working with a binary tree data structure that represents a family tree. You want to find the maximum width of this tree, which means the largest number of family members present at any single generation level.

🎯 Goal: Build a Go program that creates a binary tree, sets up a queue for level order traversal, calculates the maximum width of the tree, and prints the result.

📋 What You'll Learn

Create a binary tree with exactly 7 nodes with values 1 to 7 arranged as a complete binary tree

Create a queue to help with level order traversal

Implement the logic to find the maximum width of the binary tree

Print the maximum width as an integer

💡 Why This Matters

🌍 Real World

Binary trees are used in many applications like family trees, file systems, and decision trees. Knowing the maximum width helps understand the breadth of data at each level.

💼 Career

Understanding tree traversal and width calculation is important for software engineers working with hierarchical data, databases, and algorithms.

1

Create the binary tree nodes

Create a binary tree with a root node called root of type *TreeNode. The tree should have these exact nodes and structure:
1 as root, 2 as left child of root, 3 as right child of root, 4 as left child of node 2, 5 as right child of node 2, 6 as left child of node 3, and 7 as right child of node 3.

DSA Go

package main

import "fmt"

// TreeNode represents a node in the binary tree
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func main() {
    // Create the binary tree nodes here
    // Your code here
}

Hint

Start by creating the root node with value 1. Then assign its left and right children with values 2 and 3 respectively. Continue assigning children for nodes 2 and 3 as described.

2

Create a queue for level order traversal

Create a slice of *TreeNode called queue and initialize it with the root node. This queue will help us visit nodes level by level.

DSA Go

package main

import "fmt"

// TreeNode represents a node in the binary tree
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

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

    // Create a queue slice with root node
    // Your code here
}

Hint

Initialize the queue slice with the root node inside curly braces.

3

Calculate the maximum width of the binary tree

Write code to calculate the maximum width of the binary tree using the queue. Use a variable maxWidth initialized to 0. Use a for loop that runs while len(queue) > 0. Inside the loop, get the current level size with levelSize := len(queue). Update maxWidth if levelSize is greater. Then, use a for loop from 0 to levelSize to dequeue nodes from queue and enqueue their children if they exist.

DSA Go

package main

import "fmt"

// TreeNode represents a node in the binary tree
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

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

    queue := []*TreeNode{root}

    // Calculate maxWidth using queue
    // Your code here
}

Hint

Use a while loop with len(queue) > 0. Inside, get the current level size. Update maxWidth if needed. Then dequeue each node of this level and enqueue their children.

4

Print the maximum width

Print the value of maxWidth using fmt.Println(maxWidth).

DSA Go

package main

import "fmt"

// TreeNode represents a node in the binary tree
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

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

    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)
            }
        }
    }

    // Print the maximum width
    // Your code here
}

Hint

Use fmt.Println(maxWidth) to print the maximum width.