মডিউল ১৯-৪ঃ Diameter Of Binary Tree (Coding Ninjas)

প্রবলেম লিংকঃ Diameter Of Binary Tree - Coding Ninjas

প্রবলেম স্টেটমেন্টঃ একটি বাইনারি ট্রি দেওয়া থাকবে। তার ডায়ামিটার এর লেন্থ বের করতে হবে। এক্ষেত্রে ডায়ামিটার হচ্ছে যেকোন দুইটি নোডের মধ্যে ম্যাক্সিমাম ডিস্টেন্স।

যেমন এই ট্রি এর ক্ষেত্রে ডায়ামিটার হবে এরকমঃ

আন্সার হবে এক্ষেত্রে ৬। কারন এই ট্রিতে যেকোন দুইটি নোডের মধ্যে সবচেয়ে বেশি দূরত্ব হচ্ছে ৬। সল্যুশনঃ এক্ষেত্রে আমরা প্রতিটি নোডে যেয়ে তার লেফট সাবট্রি এর ম্যাক্সিমাম হাইট এবং রাইট সাবট্রি এর ম্যাক্সিমাম হাইট যোগ করলেই আমরা রেজাল্ট পেয়ে যাব। আমরা রিকারশন এবং গত মডিউলে দেখা ম্যাক্সিমাম হাইট বের করার কোড দিয়ে খুব সহজেই করে ফেলতে পারব।

int mx = 0;           // ম্যাক্সিমাম ডায়ামিটার স্টোর রাখার জন্য একটি ম্যাক্স ভেরিয়েবল নিয়ে নিচ্ছি।
int maxHeight(TreeNode<int> *root)
{
    if (root == NULL)          // যদি রুট নাল হয় তাহলে ০ রিটার্ন করা হচ্ছে।
        return 0;
    int l = maxHeight(root->left);   // লেফট সাবট্রি এর ম্যাক্স হাইট বের করে আনা হচ্ছে।    
    int r = maxHeight(root->right);  // রাইট সাবট্রি এর ম্যাক্স হাইট বের করে আনা হচ্ছে।
    int d = l + r;            // লেফট রাইট যোগ করে ডায়ামিটার বের করা হচ্ছে। 
    mx = max(mx, d);          // ম্যাক্স ভেলু আপডেট করা হচ্ছে।
    return max(l, r) + 1;     // লেফট এবং রাইট এর মধ্যে যেটি বড় সেটির সাথে ১ যোগ করে রিটার্ন করা হচ্ছে। বর্তমানে যেই হাইটে আছি সেটি যোগ করার জন্য মূলত ১ যোগ করা হয়েছে।
}
int diameterOfBinaryTree(TreeNode<int> *root)
{
    mx = 0;      // শুরুতে ম্যাক্স ভেরিয়েবলকে ০ দিয়ে ইনিশিয়াল করা হচ্ছে।
    int l = maxHeight(root->left);     // লেফট সাবট্রি এর ম্যাক্স হাইট বের করে আনা হচ্ছে।
    int r = maxHeight(root->right);    // রাইট সাবট্রি এর ম্যাক্স হাইট বের করে আনা হচ্ছে।
    return max(mx, l + r);        // লেফট সাবট্রি এর ম্যাক্স হাইট এবং রাইট সাবট্রি এর ম্যাক্স হাইট যোগ করা হচ্ছে এবং আমাদের ম্যাক্স ভেরিয়েবল এর সাথে যেটি ম্যাক্স সেটি রিটার্ন করা হচ্ছে।
}