#include #include using namespace std; // struct TreeNode { // int val; // TreeNode* left; // TreeNode* right; // TreeNode(int x) : val(x), left(NULL), right(NULL) {} // }; struct Pair { TreeNode* node; int index; Pair(TreeNode* node, int index) : node(node), index(index) {} }; class Solution { public: // Method to find the maximum width of the binary tree int widthOfBinaryTree(TreeNode* root) { if (root == nullptr) return 0; queue q; q.push(Pair(root, 0)); // Add the root node with position 0 int maxWidth = 0; // Initialize maximum width // Level order traversal using queue while (!q.empty()) { int size = q.size(); int minIndex = q.front().index; // Get the minimum index at this level to normalize positions int first = 0, last = 0; for (int i = 0; i < size; i++) { Pair current = q.front(); q.pop(); TreeNode* node = current.node; int index = current.index - minIndex; // Normalize the index to prevent overflow // Record the first and last positions at the current level if (i == 0) first = index; if (i == size - 1) last = index; // Enqueue left child with the correct position if it exists if (node->left) { q.push(Pair(node->left, 2 * index)); } // Enqueue right child with the correct position if it exists if (node->right) { q.push(Pair(node->right, 2 * index + 1)); } } // Calculate the width of the current level and update maxWidth maxWidth = max(maxWidth, last - first + 1); } return maxWidth; } }; int main() { Solution sol; // Create the first example tree TreeNode* example1 = new TreeNode(1); example1->left = new TreeNode(2); example1->right = new TreeNode(3); example1->left->left = new TreeNode(4); example1->right->right = new TreeNode(5); // Create the second example tree TreeNode* example2 = new TreeNode(1); example2->left = new TreeNode(2); example2->right = new TreeNode(3); example2->left->left = new TreeNode(4); example2->left->left->right = new TreeNode(7); example2->right->left = new TreeNode(5); example2->right->right = new TreeNode(6); // Create the third example tree TreeNode* example3 = new TreeNode(1); example3->left = new TreeNode(2); example3->left->left = new TreeNode(3); example3->left->right = new TreeNode(4); example3->left->right->left = new TreeNode(5); // Test the widthOfBinaryTree method with the example trees cout << sol.widthOfBinaryTree(example1) << endl; // Output: 4 cout << sol.widthOfBinaryTree(example2) << endl; // Output: 4 cout << sol.widthOfBinaryTree(example3) << endl; // Output: 2 return 0; }