মডিউল ১৯-২ঃ STL Pair, Node Level (Coding Ninjas)

আজকে প্রবলেম সল্ভ করার আগে আমরা একটি নতুন STL শিখব। সেটি হলো pair। pair এ একই সাথে যেকোন ডাটা টাইপের দুটি ডাটা জোড়া আকারে রাখা যায়। Syntax: pair<data_type, data_type> pair_name;

Example:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    pair<string,int>p;     // স্ট্রিং এবং ইন্টিজার টাইপের একটি পেয়ার নেওয়া হয়েছে। 
    p.first = "Hello";     // পেয়ার এর প্রথম ভেলু এক্সেস করা যায়  .first দিয়ে। 
    p.second = 2;          // পেয়ার এর প্রথম ভেলু এক্সেস করা যায়  .second দিয়ে। 
    cout << p.first << " " << p.second << endl;   // পেয়ার প্রিন্ট করা হচ্ছে।
}

এবার আমরা একটি প্রবলেম সল্ভ করব।

প্রবলেম লিংকঃ Node Level - Coding Ninjas

প্রবলেম স্টেটমেন্টঃ একটি বাইনারি ট্রি দেওয়া আছে এবং একটি নোড এর ভেলু দেওয়া আছে। বলতে হবে ঐ নোডের লেভেল কত। এক্ষেত্রে রুট নোডের লেভেল ১ অর্থাৎ লেভেল ১ থেকে শুরু হবে। সল্যুশনঃ আমরা গত মডিউলে দেখে আসা লেভেল অর্ডার ট্রাভারসাল এর কোড ব্যাবহার করে খুব সহজেই এটি করে ফেলতে পারি। এক্ষেত্রে আমরা ইন্টিজার টাইপের কিউ ব্যবহার করতাম লেভেল অর্ডারে নোড স্টোর করার জন্য। এবার আমরা শুধু নোড স্টোর করব না, প্রতিটি নোডের সাথে তার লেভেল ও স্টোর করব। তাই আমরা পেয়ার টাইপের কিউ ব্যবহার করব। একটি পেয়ারে আমরা নোড এবং তার লেভেল রাখব। রুটের লেভেলকে ১ দিয়ে ইনিশিয়াল করে দিব। এরপর প্রতিবার অন্য লেভেলে গেলে লেভেল এর মান ১ করে বাড়িয়ে দিব। এভাবে আমাদের কিউ তে সবগুলো নোডের সাথে সাথে তাদের লেভেল ও স্টোর থাকবে। তারপর যখনি আমরা আমাদের কাঙ্ক্ষিত নোডে চলে আসব, তখন তার লেভেল রিটার্ন করে দিব।

#include <bits/stdc++.h>
int nodeLevel(TreeNode<int> *root, int searchedValue)
{
    queue<pair<TreeNode<int> *, int>> q;     // আমরা শুধু নোড স্টোর করব না, প্রতিটি নোডের সাথে তার লেভেল ও স্টোর করব। তাই আমরা পেয়ার টাইপের কিউ নিচ্ছি।
    q.push({root, 1});       // শুরুতে কিউতে রুট নোডকে পুশ করা হচ্ছে এবং তার লেভেল হিসেবে ১ দেওয়া হচ্ছে। এক্ষেত্রে {} এর মধ্যে কমা দিয়ে দুটি ভেলু দিলে তা একটি পেয়ার গঠন করে।
    while (!q.empty())      // কিউ এম্পটি না হওয়া পর্যন্ত লুপ চলবে।
    {
        pair<TreeNode<int> *, int> pr = q.front();   // কিউ এর প্রথমে থাকা পেয়ার বের করে নেওয়া হচ্ছে।
        TreeNode<int> *node = pr.first;     // পেয়ার এর প্রথম এলিমেন্টটি হচ্ছে নোড।
        int level = pr.second;           // দ্বিতীয়টি হচ্ছে লেভেল।
        q.pop();                       // কিউ পপ করে দেওয়া হচ্ছে। 

        if (node->val == searchedValue)   // চেক করে দেখা হচ্ছে এই নোডটিই আমাদের কাঙ্ক্ষিত নোড কিনা।
        {
            return level;         // হলে তার লেভেল রিটার্ন করা হচ্ছে। 
        }
        if (node->left)           // যদি নোডের লেফট চাইল্ড থাকে তাহলে 
        {
            q.push({node->left, level + 1});   // কিউ তে পুশ করা হচ্ছে লেফট চাইল্ড এবং তার লেভেল হিসেবে বর্তমান লেভেল থেকে ১ বাড়িয়ে দেওয়া হচ্ছে।
        }
        if (node->right)         // যদি নোডের রাইট চাইল্ড থাকে তাহলে 
        {
            q.push({node->right, level + 1});   // কিউ তে পুশ করা হচ্ছে রাইট চাইল্ড এবং তার লেভেল হিসেবে বর্তমান লেভেল থেকে ১ বাড়িয়ে দেওয়া হচ্ছে।
        }
    }
}