Maximum Width of Binary Tree in DSA Go - Time & Space Complexity

Time Complexity: Maximum Width of Binary Tree

O(n)

Understanding Time Complexity

We want to understand how the time needed to find the maximum width of a binary tree grows as the tree gets bigger.

Specifically, how does the number of nodes affect the work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

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

This code finds the maximum width of a binary tree by level-order traversal, tracking node positions.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The outer loop runs once per level of the tree, and the inner loop processes every node at that level.
• How many times: Each node is visited exactly once during the traversal.

How Execution Grows With Input

As the number of nodes (n) increases, the code visits each node once, so the total work grows directly with n.

Input Size (n)	Approx. Operations
10	About 10 visits and checks
100	About 100 visits and checks
1000	About 1000 visits and checks

Pattern observation: The work grows linearly with the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the maximum width grows in direct proportion to the number of nodes in the tree.

Common Mistake

[X] Wrong: "The time complexity depends on the maximum width of the tree, not the total nodes."

[OK] Correct: Even if the width is large, the algorithm must visit every node once, so total nodes determine the time, not just the width.

Interview Connect

Understanding how tree traversal time grows helps you explain your approach clearly and shows you know how to analyze algorithms well.

Self-Check

"What if we used recursion instead of a queue for level-order traversal? How would the time complexity change?"