Maximum Width of Binary Tree

Problem Summary

• Given a binary tree, return the maximum width of it
• Remember, maximum width also includes all possible nodes that could have been placed between the left-most & right-most node

What is Being Asked?

• Calculate how many nodes could exist on a level between the left & right most node on the level

Why This Works

• Math formula to index left child: $2\ast index$
• Math formula to index right child: $2\ast index+1$

Main Concepts Used

• Trees
• Level-order Traversal
• Breadth First
• Tree Traversal

Time & Space Complexity

• Time: $O(n)$ → Reason: Processing each node
• Space: $O(width)$ → Reason: $2^{n-1}$ number of nodes at the last level or $O(n)$

Code

class Solution:
    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        q = deque([(root, 1)])
        max_width = 0
        while q:
            left_most_index = q[0][1]
            right_most_index = q[-1][1]
            max_width = max(max_width, abs(left_most_index - right_most_index) + 1)
            for _ in range(len(q)):
                node, index = q.popleft()
                if node.left:
                    q.append((node.left, (index * 2)))
                if node.right:
                    q.append((node.right, (index * 2) + 1))
        return max_width

Common Mistakes / Things I Got Stuck On

• Appending None children of node
• Not using $(index\ast 2)+1$ to count the number of nodes