মডিউল ১৯-৫ঃ Special Binary Tree (Coding Ninjas)

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

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

#include <bits/stdc++.h>
bool isSpecialBinaryTree(BinaryTreeNode<int> *root)
{
    if (root->left == NULL && root->right == NULL)   // যদি লেফট, রাইট দুটিই নাল হয় তারমানে কোন চাইল্ড নেই। তাই রিটার্ন ট্রু।
        return true;
    if (root->left == NULL || root->right == NULL)   // উপরের কন্ডিশন সত্য না হলে এখানে আসবে। এখন চেক করে দেখা হচ্ছে লেফট, রাইট দুটির মধ্যে যেকোন একটি নাল কিনা। নাল হলে রিটার্ন ফলস। 
        return false;
    bool l = isSpecialBinaryTree(root->left);     // উপরের কন্ডিশন সত্য না হলে দুটি চাইল্ড ই আছে। তাই দুটি চাইল্ড পাঠিয়ে দেওয়া হচ্ছে রিকারশনে।
    bool r = isSpecialBinaryTree(root->right);
    if (l == false || r == false)     // দুটি চাইল্ড এর মধ্যে যেকোন একটি যদি ফলস হয় তাহলে রিটার্ন ফলস।
        return false;
    return true;      // নাহলে রিটার্ন ট্রু।
}