Leetcode 662. Maximum Width of Binary Tree

Problem: Maximum Width of Binary Tree

In this problem, we are given a binary tree where each node has left and right children which may or may not be null. The task is to write a function that calculates the maximum width of the given binary tree. The maximum width of a tree is the maximum number of nodes at any level.

The width of a level in the tree is defined as the number of nodes between the leftmost and rightmost nodes at that level, including null nodes.

Consider the following example:

Example 1:

Input:

1
2
3           1
4         /   \
5        3     2
6       / \     \
7      5   3     9

Output: 4

At the third level of the tree, we have 4 nodes (5, 3, null, 9). Hence, the maximum width at any level is 4.

Solution: Breadth-First Search

We can solve this problem by performing a Breadth-First Search (BFS) on the tree. This is because breadth-first allows us to traverse all nodes at a certain 'width' or level of the tree before moving on to the next level. Thus, we can calculate the width of each level and return the maximum.

Although the nodes in the tree do not have indices, we can imagine assigning each node an index based on its position from the left at each level. For instance, the root could have an index of 1, its left child an index of 2, and its right child an index of 3 (assuming we start counting from 1). For any node at index i, its left child will have an index of 2i and its right child will have an index of 2i+1.

Python Solution

1
2python
3from collections import deque
4
5class Solution:
6    def widthOfBinaryTree(self, root):
7        if not root:
8            return 0
9
10        max_width = 0
11        queue = deque([(root, 1)])
12
13        while queue:
14            max_width = max(max_width, queue[-1][1] - queue[0][1] + 1)
15
16            for _ in range(len(queue)):
17                node, idx = queue.popleft()
18                if node.left:
19                    queue.append((node.left, idx*2))
20                if node.right:
21                    queue.append((node.right, idx*2 + 1))
22
23        return max_width

This Python solution begins by checking if the tree has any nodes at all. If it does not, we return 0.

It then uses a deque called queue to hold the nodes to be inspected, along with their indices. As nodes are inspected, their children are added to the queue with the appropriate index calculation.

The max_width variable holds the maximum width found at any particular level of the tree during the BFS.

Java Solution

1
2java
3class Solution {
4    public int widthOfBinaryTree(TreeNode root) {
5        if (root == null) {
6            return 0;
7        }
8
9        Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
10        queue.offer(new Pair(root, 1));
11        int max_width = 0;
12
13        while (!queue.isEmpty()) {
14            int size = queue.size();
15            int start = queue.peek().getValue();
16            int end = start;
17           
18            for (int i = 0; i < size; i++) {
19                Pair<TreeNode, Integer> pair = queue.poll();
20                TreeNode node = pair.getKey();
21                int idx = pair.getValue();
22                end = idx;
23
24                if (node.left != null) {
25                    queue.offer(new Pair(node.left, idx * 2));
26                }
27               
28                if (node.right != null) {
29                    queue.offer(new Pair(node.right, idx * 2 + 1));
30                }
31            }
32            max_width = Math.max(max_width, end - start + 1);
33        }
34       
35        return max_width;
36    }
37}
38
39// Assume TreeNode and Pair are previously defined as:
40
41class TreeNode {   
42    TreeNode left, right;
43}
44
45class Pair<K, V> {
46    private K key;
47    private V value;
48    // getters, setters, constructors omitted for brevity
49}

JavaScript Solution

1
2javascript
3var widthOfBinaryTree = function(root) {
4    if (!root) return 0;
5    
6    let queue = [[root, 1]], maxWidth = 0;
7    
8    while (queue.length > 0) {
9        let levelWidth = queue[queue.length - 1][1] - queue[0][1] + 1;
10        maxWidth = Math.max(maxWidth, levelWidth);
11        
12        let len = queue.length;
13        for (let i = 0; i < len; i++) {
14            let node = queue.shift();
15
16            if (node[0].left) queue.push([node[0].left, node[1] * 2]);
17            if (node[0].right) queue.push([node[0].right, node[1] * 2 + 1]);
18        }
19    }
20    
21    return maxWidth;
22};
23
24// Assume TreeNode is previously defined as:
25
26class TreeNode {
27  constructor(val, left, right) {
28    this.val = (val===undefined ? 0 : val);
29    this.left = (left===undefined ? null : left);
30    this.right = (right===undefined ? null : right);
31  }
32}

The JavaScript solution starts by checking if the root is null, and if it is, we return 0 as there is no width in this case.

After that, we initialize a queue to contain an array of nodes and their respective indices. The maxWidth is initialized to 0.

Then there’s a while loop that continues as long as there are nodes in the queue. Inside the loop, we calculate the width of the current level by subtracting the index of the first node in the queue from the index of the last node in the queue and adding 1. We then update our maxWidth if the current level's width is greater than the previous maxWidth.

After calculating the width, we loop over all the nodes at the current level by shifting them out from the queue. If the node has a left child, we push the child and its index to the queue. If the node has a right child, we also push the child and its index to the queue.

After we finish processing all nodes at the current level (i.e., the for loop ends), we start the next iteration of the while loop, which now will process the next level. The loop continues until the queue is empty, which means all nodes have been processed.

Finally, we return the maxWidth.

In summary, solving the maximum width of a binary tree problem requires traversing the tree level by level while calculating the width of each level. We then return the maximum width found. We achieved this in Python, Java, and JavaScript using Queues and Pair data structures for storing nodes and their artificial indices.