jayati

Maximum Width of Binary Tree

Apr 19th, 2023
179
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.36 KB | None | 0 0
  1. class Solution {
  2. public:
  3.     int widthOfBinaryTree(TreeNode* root) {
  4.         if(root == NULL)
  5.             return 0;
  6.        
  7.         int res = 1;
  8.         queue<pair<TreeNode*, int>> q;
  9.        
  10.         // I am using intialising list
  11.         q.push({root, 0});      // also can use make_pair
  12.        
  13.         while(!q.empty())
  14.         {
  15.             int cnt = q.size();
  16.             // start is the index of root node for first level
  17.             int start = q.front().second;
  18.             int end = q.back().second;
  19.            
  20.             res = max(res,end-start + 1);
  21.            
  22.             for(int i = 0; i <cnt; ++i)
  23.             {
  24.                 pair<TreeNode*, int> p = q.front();
  25.                 // we will use it while inserting it children
  26.                 // left child will be 2 * idx + 1;
  27.                 // right chils will be 2 * idx + 2;
  28.                 int idx = p.second - start;
  29.                
  30.                 q.pop();
  31.                
  32.                 // if  left child exist
  33.                 if(p.first->left != NULL)
  34.                     q.push({p.first->left, (long long)2 * idx + 1});
  35.                
  36.                 // if right child exist
  37.                 if(p.first->right != NULL)
  38.                     q.push({p.first->right, (long long) 2 * idx + 2});
  39.             }
  40.         }
  41.        
  42.         return res;
  43.        
  44.     }
  45. };
Advertisement
Add Comment
Please, Sign In to add comment