Maximum Width of Binary Tree

Link

Description

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 that would be present in a complete binary tree extending down to that level are also counted into the length calculation.

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

Example 1:

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

Example 2:

• Input: root = [1,3,2,5,null,null,9,6,null,7]
• Output: 7
• Explanation: The maximum width exists in the fourth level with length 7 (6,null,null,null,null,null,7).

Example 3:

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

Constraints:

• The number of nodes in the tree is in the range [1, 3000].
• -100 <= Node.val <= 100

Solution

BFS

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        if (!root) return 0;
        size_t res = 1;  // use size_t to prevent overflow
        queue<pair<TreeNode*, size_t>> que;
        que.push({root, 1LL});

        while (!que.empty()) {
            size_t len = que.size();
            size_t start = que.front().second;
            size_t end = que.back().second;
            res = max(res, end - start + 1);

            while (len--) {
                auto [node, index] = que.front();
                que.pop();

                if (node->left) {
                    que.push({node->left, index * 2});
                }
                if (node->right) {
                    que.push({node->right, index * 2 + 1LL});
                }
            }
        }

        return res;
    }
};

Time Complexity:

1. Breadth-First Search (BFS): The algorithm uses a breadth-first search strategy to traverse the tree. In BFS, each node is visited exactly once. Therefore, the time complexity is directly proportional to the number of nodes in the tree.
2. Operations per Node: For each node visited, the algorithm performs a constant amount of work, including checking the existence of child nodes, calculating indices, and updating the maximum width. These operations take constant time \(O(1)\) per node.
3. Total Time Complexity: Since each node is visited once and a constant amount of work is done for each node, the total time complexity of the algorithm is \(O(N)\), where \(N\) is the total number of nodes in the binary tree.

Space Complexity:

1. Queue Storage: The algorithm uses a queue to store the nodes of the tree along with their indices at each level of the breadth-first search. In the worst-case scenario, the queue needs to store all nodes at the widest level of the tree. For a perfectly balanced binary tree, this could be up to \(\frac{N}{2}\) nodes (in the last level). However, the tree could be skewed, resulting in a space complexity that is less than this theoretical maximum in balanced cases.

2. Index Representation: The indices of the nodes might grow large, especially for deep trees, but this does not significantly affect the space complexity in terms of the number of elements stored in the queue. The space required to store each index is constant, but it's worth noting that we must ensure the data type used for indices can handle large values to prevent overflow.

3. Total Space Complexity: The dominant factor in space complexity is the queue storage, which, in the worst-case scenario, could require space proportional to the maximum width of the tree. Therefore, the space complexity is \(O(W)\), where \(W\) is the maximum number of nodes at any level of the tree.

DFS

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    unordered_map<int, size_t> mapping;
    int res = 0;

    void dfs(TreeNode* root, size_t u, int depth) {
        if (!root) return;

        if (mapping.find(depth) == mapping.end()) mapping[depth] = u;
        res = max(res, static_cast<int>(u - mapping[depth] + 1));
        dfs(root->left, u * 2, depth + 1);
        dfs(root->right, u * 2 + 1, depth + 1);
    }

public:
    int widthOfBinaryTree(TreeNode* root) {
        dfs(root, 1, 0);
        return res;
    }
};