মডিউল ১৮-৭ঃGet the Maximum Height of a Binary Tree

গত মডিউল গুলোতে আমরা দেখেছি কিভাবে Recursion এর সাহায্যে কোনো বাইনারী ট্রি এর Node এর কাউন্ট , কয়টি Leaf Node আছে তার কাউন্ট বের করা শিখেছি। Guess what ? এই প্রবলেম সল্ভ করার জন্য ও আমরা ঠিক একই ভাবে Recursive ওয়ে তে চিন্তা করে খুব সহজে সমস্যাটি সমাধান করে নিতে পারবো।

প্রথমে জেনে নেয়া যাক , কোনো একটি Binary Tree এর Maximum height কাকে বলে।

Root হতে সবচেয়ে দূরের Node এর মাঝে যত সংখ্যক Node আছে তাকে ঐ Binary Tree এর Maximum Node বলা হয়ে থাকে।

এখন দেখে নেয়া যাক , কীভাবে আমরা Recursive ওয়ে তে প্রবলেম টি চিন্তা করতে পারি

আমরা এমন একটি ফাংশন তৈরি করবো যেখানে আমরা একটি Binary Tree এর Root Node পাস করলে , ঐ ফাংশন টি আমাদের ঐ Binary Tree এর Maximum Height টি বের করে দিবে। এখন আমাদের কাজ হবে ঠিক ভাবে এই ভাবনা টা কে কাজে লাগানো এবং একটি Proper base case সেট করা

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

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

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

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

• সবশেষে যেহেতু আমাকে Maximum Height টি বের করতে হবে , আমি Left subtree এর Maximum Height এবং Right subtree এর Maximum Height টি কম্পেয়ার করে দেখবো কোনটি Maximum তার সাথে ১ যোগ করে তা রিটার্ন করবো। ১ যোগ করার কারণে Root Node এর জন্য পুরো Tree এর Maximum Height এ একটি 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 এর Root Node দেয়া হলে তা ঐ Binary Tree এর Maximum Height Return করে  
int maxHeight(Node *root)
{ 
   // Tree টি খালি হলে তার Maximum Height ০ হবে 
    if (root == NULL)
        return 0;
    int l = maxHeight(root->left); // Left subtree এর Maximum Height কত তা maxHeight ফাংশনের মাধ্যমে বের  করা হচ্ছে
    // এই ক্ষেত্রে Left subtree এর Root হলো current root Node এর left child
    int r = maxHeight(root->right);// Right subtree এর Maximum Height কত তা maxHeight ফাংশনের মাধ্যমে বের  করা হচ্ছে
    // এই ক্ষেত্রে Right subtree এর Root হলো current root Node এর right child
   
    return max(l, r) + 1; // এরপর left এবং right এর মধ্যে compare করে max height টি নিবো এবং তার সাথে ১ যোগ করে Return করে দিবো। 
}
int main()
{
    Node *root = input_tree();
    cout << maxHeight(root) << endl;
    return 0;
}