[662. Maximum Width of Binary Tree](https://leetcode.com/problems/maximum-width-of-binary-tree/)

--- tags: leetcode --- # [662. Maximum Width of Binary Tree](https://leetcode.com/problems/maximum-width-of-binary-tree/) --- # My Solution ## The Key Idea for Solving This Coding Question BFS ## C++ Code ```cpp= /** * 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) {} * }; */ struct nodeData { TreeNode *node; unsigned long id; nodeData() : node(nullptr), id(-1) {} nodeData(TreeNode *node, unsigned long id) : node(node), id(id) {} }; class Solution { public: int widthOfBinaryTree(TreeNode *root) { queue<nodeData> q; unsigned long width = 0; q.push(nodeData(root, 1)); while (!q.empty()) { int qLen = q.size(); unsigned long firstId = q.front().id, lastId; for (int i = 0; i < qLen; ++i) { nodeData curr = q.front(); lastId = curr.id; q.pop(); if (curr.node->left != nullptr) { q.push(nodeData(curr.node->left, curr.id * 2)); } if (curr.node->right != nullptr) { q.push(nodeData(curr.node->right, curr.id * 2 + 1)); } } width = max(width, lastId - firstId + 1); } return static_cast<int>(width); } }; ``` ## Time Complexity $O(n)$ $n$ is the number of nodes in the binary tree referred by `root`. ## Space Complexity $O(n)$ $n$ is the number of nodes in the binary tree referred by `root`. # Miscellane