১৮-৫ঃ Count Number of Nodes of a Binary Tree

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

Binary Tree এর Node সংখ্যা কাউন্ট করা সহজ একটি কাজ যদি আমরা Recursion ভালো মতো বুঝে থাকি । আমরা জানি Recursion এর মাধ্যমে আমরা একটি কাজ বারবার ঐ ফাংশন কল করার মাধ্যমে করে নিতে পারি। এইক্ষেত্রেও ঠিক একই ভাবে শুধুমাত্র একটি ফাংশনের সাহায্যে আমরা Node কাউন্ট করার কাজটি করে নিতে পারবো । তার জন্য শুধু মাত্র প্রয়োজন ঠিক মতো Recursion ব্যবহার করতে পারা , and most importantly বুঝতে পারা আমাদের যে ফাংশন টি আছে তার কাজটা কী। আমরা যেহেতু একটি Binary tree এর Node সংখ্যা কাউন্ট করবো , তাই আমাদের ফাংশনের কাজ হবে যদি তাকে একটি Root Node দিয়ে দেয়া হয় তবে সে ঐ Root এর Binary Tree তে কয়টি Node আছে তা আমাদের রিটার্ন করে দিবে । এখন আমরা কিছু Question করার মাধ্যমে আমাদের Recursion ফাংশন টি তৈরি করবো ।

• প্রথমত , আমরা যদি Binary Tree এর Node টি ফাংশনে পাস করি , এবং Root যদি Null না হয় , তবে আমরা এতটুকু নিশ্চিত যে , আমরা মিনিমাম একটি Node তো পেয়েছি ।

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

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

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

• সবশেষে Left Subtree তে কয়টি Node আছে এবং Right Subtree তে কয়টি Node আছে তা জানার পর , আমরা Main Root Node এর জন্য ১ যোগ করে , পুরো Binary Tree তে কয়টি Node আছে তা রিটার্ন করে দিতে পারি।

খেয়াল রাখতে হবে , ফাংশনের base case যাতে ঠিক মতো সেট করা থাকে। এখন চিন্তা করে দেখা যাক , Base case কী হতে পারে । প্রথমে আমরা চিন্তা করতেসিলাম , যদি Root Node টি null নাহয় তবে সেক্ষেত্রে আমরা একটি হলেও Node পাবো তা guaranteed. এখন Root যদি নিজেই Null হয় তবে সেক্ষেত্রে তার তো কোনো Children থাকবে না , যেহতু তার ই কোনো অস্তিত্ব নেই। এক্ষেত্রে আমরা left এ কয়টি Node আছে বা right এ কয়টি Node আছে তা না দেখে সরাসরি 0 return করতে পারি। কারণ এই Tree তে কোনো Node ই নেই। আসুন , এইবার সহজ সরল এই approach এর কোডটি লিখে ফেলা যাক।

#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 এর Root দিলে তাতে কয়টি Node আছে তা বলে দেয়
int count(Node *root) 
{
    if (root == NULL) // যদি Root Null হয় তবে Tree টিতে কোনো Node নেই
        return 0;
    int l = count(root->left); // Left subtree তে কয়টি Node আছে তা count ফাংশনের মাধ্যমে কাউন্ট করা হচ্ছে
    // এই ক্ষেত্রে Left subtree এর Root হলো current root Node এর left child
    int r = count(root->right);// Right subtree তে কয়টি Node আছে তা count ফাংশনের মাধ্যমে কাউন্ট করা হচ্ছে
    // এই ক্ষেত্রে Right subtree এর Root হলো current root Node এর right child
    return l + r + 1; // left subtree এবং right subtree এর Node সংখ্যার সাথে Root node এর কাউন্ট ১ যোগ করে রিটার্ন করা হচ্ছে
}


int main()
{
    Node *root = input_tree();
    cout << count(root) << endl;
    return 0;
}