ধরা যাক একটি বাইনারি ট্রি আছে, আমরা ট্রির সর্বোচ্চ প্রস্থ (maximum width) বের করার ফাংশন লিখব। এখানে ট্রির প্রস্থ বলতে সব লেভেলের প্রস্থের মধ্যে সর্বোচ্চটিকে বুঝায়। আমরা বিবেচনা করব বাইনারি ট্রিটি একটি ফুল বাইনারি ট্রির মতো কাঠামো রাখে, কিন্তু কিছু নোড null। একটি লেভেলের প্রস্থ আসলে সেই লেভেলের শেষ নোডগুলোর (বামপাশের এবং ডানপাশের নন-নাল নোড) মধ্যকার দৈর্ঘ্য, যেখানে শেষ নোডের মধ্যকার null নোডগুলোও দৈর্ঘ্য গণনায় যোগ করা হয়। যদি ট্রি নিচের মতো হয় −
তবে সর্বোচ্চ প্রস্থ হবে 4, কারণ শেষ লെയারের নোডগুলো হলো [5,3,null,9]
সমাধানের ধাপগুলো −
ans := 1, size := 0
একটি ডবল-এন্ডেড কিউ q সংজ্ঞা করব যেখানে (node, value) জোড়া স্টোর করব।
(root, 1) q-তে ইনসার্ট করব
যখন q খালি নয়
size := q-এর আকার
একটি (node, value) জোড়া curr সংজ্ঞা করব
যদি size 1 হয়, তবে (q-এর ফ্রন্ট এলিমেন্টের নোড, 1) q-তে ইনসার্ট করব, q থেকে ডিকিউ করব
যখন size ০ নয়
curr := q-এর ফ্রন্ট এলিমেন্ট, q থেকে ফ্রন্ট ডিকিউ করব
যদি curr নোডের বাম নাল নয়, তবে
(curr নোডের বাম, 2 * curr-এর value) তৈরি করে q-তে ইনসার্ট করব
যদি curr নোডের ডান নাল নয়, তবে
(curr নোডের ডান, 2 * curr-এর value + 1) তৈরি করে q-তে ইনসার্ট করব
যদি q-এর আকার > 1 হয়, তবে
ans := ans এবং (q-এর লাস্ট এলিমেন্টের value - q-এর ফার্স্ট এলিমেন্টের value + 1)-এর ম্যাক্সিমাম
size := size - 1
ans রিটার্ন করব
নিচের ইমপ্লিমেন্টেশন দেখুন −
উদাহরণ
#include <bits/stdc++.h> using namespace std; class TreeNode{ public: int val; TreeNode *left, *right; TreeNode(int data){ val = data; left = NULL; right = NULL; } }; void insert(TreeNode **root, int val){ queue<TreeNode*> q; q.push(*root); while(q.size()){ TreeNode *temp = q.front(); q.pop(); if(!temp->left){ if(val != NULL) temp->left = new TreeNode(val); else temp->left = new TreeNode(0); return; }else{ q.push(temp->left); } if(!temp->right){ if(val != NULL) temp->right = new TreeNode(val); else temp->right = new TreeNode(0); return; }else{ q.push(temp->right); } } } TreeNode *make_tree(vector<int> v){ TreeNode *root = new TreeNode(v[0]); for(int i = 1; i<v.size(); i++){ insert(&root, v[i]); } return root; } class Solution { public: int widthOfBinaryTree(TreeNode* root) { int ans = 0; deque < pair <TreeNode*, int> > q; q.push_back({root,1}); ans = 1; int size; while(!q.empty()){ size = q.size(); pair <TreeNode*, int> curr; if(size == 1){ q.push_back({q.front().first, 1}); q.pop_front(); } while(size--){ curr = q.front(); q.pop_front(); if(curr.first->left){ q.push_back({curr.first->left, 2 * curr.second}); } if(curr.first->right){ q.push_back({curr.first->right, 2 * curr.second + 1}); } } if(q.size() > 1) ans = max(ans, q.back().second - q.front().second + 1); } return ans; } }; main(){ vector<int> v = {1,3,2,5,3,NULL,9}; TreeNode *root = make_tree(v); Solution ob; cout << (ob.widthOfBinaryTree(root)); }ইনপুট
[1,3,2,5,3,null,9]
আউটপুট
4
