১৮-৬ঃ Count Number of Leaf Nodes of a Binary Tree

গত মডিউলে আমরা দেখেছিলাম, কীভাবে একটি Binary Tree তে কয়টি Node আছে তা বের করা যায়। এই মডিউলে আমরা দেখবো কীভাবে একটি Binary Tree তে কয়টি Leaf Node আছে তা বের করা যায়। এর জন্য প্রথমে আমাদের জানতে হবে একটি Tree এর Leaf Node কাকে বলে ।

Leaf Node: একটি ট্রি এর যে সকল Node এর কোনো Children নেই , তাদের Leaf Node বলা হয়ে থাকে।

খেয়াল করে দেখবেন Total Node কাউন্ট করার প্রবলেম এবং Leaf Node কাউন্ট করার প্রবলেমটি মোটামুটি একই। লাস্ট প্রবলেমে আমরা দেখেছিলাম কীভাবে একটি BInary Tree এর total Node বের করা যায় , এখন বের করবো Total Leaf Nodes । উভয় একই Node count করার প্রবলেম । গত প্রবলেমের মতো এই প্রবলেমটি ও আমরা Recursion দিয়ে করার চেষ্টা করবো । আমরা যেহেতু একটি Binary tree এর Leaf Node সংখ্যা কাউন্ট করবো , তাই আমাদের ফাংশনের কাজ হবে যদি তাকে একটি Root Node দিয়ে দেয়া হয় তবে সে ঐ Root এর Binary Tree তে কয়টি Leaf Node আছে তা আমাদের রিটার্ন করে দিবে ।

এখন আমরা কিছু Question করার মাধ্যমে আমাদের Recursion ফাংশন টি তৈরি করবো ।

• প্রথমত , আমরা যদি Binary Tree এর Node টি ফাংশনে পাস করি , এবং Root যদি নিজেই Null হয় তবে আমরা বলতে পারি এই Binary Tree তে কোনো Node নেই , এবং কোনো Leaf Node নেই। এক্ষেত্রে ০ রিটার্ন হবে। ( Base Case )

• যদি Root Node যদি থাকে , এবং তার যদি কোনো Left child এবং Right child না থাকে তবে সেই Node টি হবে Leaf Node. যেহেতু Left child এবং Right Child নেই সেক্ষেত্রে এর left subtree বা right subtree নেই। এক্ষেত্রে আমরা বলতে পারি এই Tree এর leaf node শুধু মাত্র একটি। ১ রিটার্ন করে দিবো ( Base Case )

• যদি উপরের কোনোটি সত্যি না হয় তবে দেখার বিষয় হলো তার Left Subtree তে কয়টি Leaf Node আছে এবং তার Right subtree তে কয়টি Leaf Node আছে ।

• যেহেতু আমরা আমাদের ফাংশন কে এমন ভাবে ডিজাইন করেছি , তাকে একটি Root Node দেয়া হলে সে আমাকে ঐ Binary Tree তে কয়টি Leaf Node আছে তা বের করে দিবে , তাই আমরা নতুন করে আর ফাংশন না লিখে Left subtree এর Root Node একই ফাংশনে pass করে তা বের করে নিতে পারবো। এক্ষেত্রে Left subtree এর Root অর্থাৎ Main Root এর Left child টি থেকে যে Tree উৎপন্ন হয়েছে , তাকে আমরা একটি Subtree বলতেছি .

• Right subtree তে কয়টি Leaf Node আছে তা বের করার জন্য আমরা একইভাবে আমাদের কাউন্ট করার ফাংশনটির হেল্প নিবো এবং তাকে Right subtree এর Root Node টি পাস করলে আমরা ঐ Subtree তে কয়টি Leaf Node আছে তা আমাকে বের করে দিবে । এক্ষেত্রে Right subtree এর Root অর্থাৎ Main Root এর Right child টি থেকে যে Tree উৎপন্ন হয়েছে , তাকে আমরা একটি Subtree বলতেছি .

• সবশেষে Left Subtree তে কয়টি Leaf Node আছে এবং Right Subtree তে কয়টি Leaf Node আছে তা জানার পর , তার যোগফল আমরা রিটার্ন করে দিবো ।

কোডের মাধ্যমে বিষয়টি আরো ভালোভাবে বুঝার চেষ্টা করি Code:

#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
    int val;
    Node *left;
    Node *right;
    Node(int val)
    {
        this->val = val;
        this->left = NULL;
        this->right = NULL;
    }
};

// বাইনারী ট্রি ইনপুট নেয়ার কোড যা গত পেজে ব্যাখ্যা করা হয়েছে। 
Node *input_tree()
{
    int val;
    cin >> val;
    Node *root;
    if (val == -1)
        root = NULL;
    else
        root = new Node(val);
    queue<Node *> q;
    if (root)
        q.push(root);
    while (!q.empty())
    {
    
        Node *p = q.front();
        q.pop();

       
        int l, r;
        cin >> l >> r;
        Node *myLeft;
        Node *myRight;
        if (l == -1)
            myLeft = NULL;
        else
            myLeft = new Node(l);
        if (r == -1)
            myRight = NULL;
        else
            myRight = new Node(r);

        p->left = myLeft;
        p->right = myRight;

        
        if (p->left)
            q.push(p->left);
        if (p->right)
            q.push(p->right);
    }
    return root;
}

// ফাংশনটি কোনো একটি Binary Tree তে কয়টি Leaf Node আছে তা বের করে দিবে
int count_leaf(Node *root)
{
    if (root == NULL) // যদি Tree তে কোনো Node না থাকে , তবে কোনো leaf node নেই
        return 0;
    // যদি কারেন্ট Binary Tree এর left child এবং right child না থাকে তবে তা একটি Leaf Node 
    if (root->left == NULL && root->right == NULL) // 
    {
        return 1; // এক্ষেত্রে 1 return হবে । 
    }
    // উপরের কোনোটি সত্যি না অর্থাৎ left child অথবা right child আছে 
    else
    {
        int l = count_leaf(root->left);// Left subtree তে কয়টি Leaf Node আছে তা count_leaf ফাংশনের মাধ্যমে কাউন্ট করা হচ্ছে
    // এই ক্ষেত্রে Left subtree এর Root হলো current root Node এর left child
        int r = count_leaf(root->right);// Right subtree তে কয়টি Leaf Node আছে তা count_leaf ফাংশনের মাধ্যমে কাউন্ট করা হচ্ছে
    // এই ক্ষেত্রে Right subtree এর Root হলো current root Node এর right child
        return l + r; // দুটি ফাংশন থেকে প্রাপ্ত leaf node সংখ্যা যোগ করে রিটার্ন করা হয়েছে। 
    }
}
int main()
{
    Node *root = input_tree();
    cout << count_leaf(root) << endl;
    return 0;
}