Given the root of a binary tree, return the maximum width of the given tree.

The maximum width of a tree is the maximum width among all levels.

The width of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end-nodes are also counted into the length calculation.

It is guaranteed that the answer will in the range of 32-bit signed integer.

Example 1

• Input: root = [1,3,2,5,3,null,9]
• Output: 4
• Explanation: The maximum width existing in the third level with the length 4 (5,3,null,9).

Example 2

• Input: root = [1,3,null,5,3]
• Output: 2
• Explanation: The maximum width existing in the third level with the length 2 (5,3).

Example 3

• Input: root = [1,3,2,5]
• Output: 2
• Explanation: The maximum width existing in the second level with the length 2 (3,2).

Approach 1: Breadth First Search (BFS)

Idea

BFS visits the tree level by level. Thus, by modifying the BFS code we can find the width of each level of the binary tree.

We know that a binary tree can be represented by an array (assuming the root begins from the position with index 1 in the array). If the index of a node is i, the indices of its left and right children are $2i$ and $2i + 1$ respectively.

Here’s how it looks:

                1
          2               3
      4       5       6       7
    8   9   # 11    12 #     # 15

# represents a null node.

Implementation

int widthOfBinaryTree(TreeNode* root) {
    if (!root) return 0;
    long maximumWidth = 0;
    // Node, index in array
    queue<pair<TreeNode*, long>> q;
    q.push({root, 1L});
    while (!q.empty()) {
        maximumWidth = max(maximumWidth, q.back().second + 1L - q.front().second);
        int n = q.size();
        while (n--) {
            TreeNode* node = q.front().first;
            int position = q.front().second;
            q.pop();
            if (node->left) {
                q.push({node->left, position * 2L});
            }
            if (node->right) {
                q.push({node->right, position * 2L + 1L});
            }
        }
    }
    return (int)maximumWidth;
}

Complexity Analysis

• Time Complexity: $O(N)$ where $N =$ number of nodes in the binary tree
• Space Complexity: $O(N)$, at the worst case of skewed tree we will need to store all the nodes in the queue

Approach 2: Depth First Search

Idea

We can use the similar technique we have used for BFS here as well. We keep record of the positions in the depthToPosition array and use it to calculate the width.

Implementation

int dfs(TreeNode *root, int depth, unsigned long long position, vector<pair<unsigned long long, unsigned long long>> &depthToPosition){
    if(root == nullptr) return 0;
    if(depthToPosition.size() == depth){
        depthToPosition.push_back({position, position});
    } else {
        depthToPosition[depth].second = position;
    }
    int cur = depthToPosition[depth].second - depthToPosition[depth].first + 1;
    int left = dfs(root -> left, depth + 1, 2ULL * position, depthToPosition);
    int right = dfs(root -> right, depth + 1, 2ULL * position + 1ULL, depthToPosition);
    return max({cur, left, right});
}
    
int widthOfBinaryTree(TreeNode* root) {
    // records position for start and end of a level respectively
    vector<pair<unsigned long long, unsigned long long>> depthToPosition;
    return dfs(root, 0, 1ULL, depthToPosition);
}

• Time Complexity: $O(N)$ where $N =$ number of nodes in the binary tree
• Space Complexity: $O(N)$, at the worst case of skewed tree we will need to store the details of all the nodes in the recursion stack