আমাদের একটি বাইনারি ট্রি দেওয়া আছে। লক্ষ্য হলো সেই ট্রিতে সর্বোচ্চ দৈর্ঘ্যের সাইকেল বের করা। এটি রুট নোড থেকে বাম ও ডান সাবট্রির সর্বোচ্চ হাইট খুঁজে সেগুলো जोড়া দিয়ে পাওয়া যায়।
উদাহরণ: ট্রি (চিত্রে) এর জন্য সর্বোচ্চ সাইকেল দৈর্ঘ্য ৬ (১-২-৩-৪-৭-৬ বা ১-৬-৭-৪-৩-২-১)।
ইনপুট
ট্রি (চিত্রে)
আউটপুট
Maximum length cycle is - 5
ব্যাখ্যা: বাম সাবট্রির ম্যাক্স হাইট ৩, ডান সাবট্রির ১। সাইকেল দৈর্ঘ্য = ৩+১+১=৫ (রুট যোগ করে)।
ইনপুট
ট্রি (চিত্রে)
আউটপুট
Maximum length cycle is - 7
ব্যাখ্যা: বাম ও ডান সাবট্রির ম্যাক্স হাইট ৩। সাইকেল দৈর্ঘ্য = ৩+৩+১=৭।
প্রোগ্রামে ব্যবহৃত পদ্ধতি
- treenode ক্লাস: data, left, right পয়েন্টার।
- newNode(int data) ফাংশন দিয়ে নোড তৈরি।
- maxheight(treenode* root) ফাংশন রিকার্সিভলি ট্রির সর্বোচ্চ হাইট রিটার্ন করে।
- রুট NULL হলে ০। লেফট ও রাইট হাইট রিকার্সিভ কল। max(lheight, rheight) + 1 রিটার্ন।
- মেইনে রুটের বাম ও ডান সাবট্রির ম্যাক্স হাইট নিয়ে যোগ করা (+১ রুটের জন্য)।
- ফলাফল প্রিন্ট।
উদাহরণ কোড
#include <bits/stdc++.h>
using namespace std;
class treenode{
public:
int data;
treenode* left;
treenode* right;
};
int maxheight(treenode* root){
if (root == NULL) return 0;
int lheight = maxheight(root->left);
int rheight = maxheight(root->right);
return max(lheight, rheight) + 1;
}
treenode* newNode(int data){
treenode* Node = new treenode();
Node->data = data;
Node->left = NULL;
Node->right = NULL;
return Node;
}
int main(){
treenode *root = newNode(6);
root->left = newNode(8);
root->right = newNode(9);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->left->right->right = newNode(7);
root->left->right->right->left = newNode(2);
int maxlheight = maxheight(root->left);
int maxrheight = maxheight(root->right);
cout << "Maximum length cycle: " << maxlheight + maxrheight + 1;
return 0;
}আউটপুট
Maximum length cycle: 6
