বাইনারি ট্রি একটি বিশেষ গাছ যার প্রতিটি নোডে সর্বোচ্চ দুটি চাইল্ড নোড থাকে। সুতরাং, প্রতিটি নোড হয় একটি লিফ নোড বা একটি বা দুটি চাইল্ড নোড রয়েছে৷
উদাহরণ,
এই সমস্যায়, আমাদের একটি বাইনারি গাছ দেওয়া হয়েছে এবং আমাদের গাছের একটি নোড রয়েছে এবং আমাদের নোডের কাজিন নোডগুলি খুঁজে বের করতে হবে। বাইনারি ট্রির জন্য কোনো ভাইবোন নোড প্রিন্ট করা হবে না।
একটি উদাহরণ নেওয়া যাক,
উপরের বাইনারি গাছের জন্য, কাজিন নোড হল 5।
ধারণাটি আরও স্পষ্ট করতে চাচাত ভাই নোড বর্ণনা করা যাক। একটি বাইনারি ট্রিতে, দুটি নোডকে কাজিন নোড বলা হয় যদি তারা বাইনারি ট্রিতে একই স্তরে (গভীরতা) থাকে কিন্তু একই প্যারেন্ট নোড না থাকে৷
এখন, এই সমস্যার একটি সমাধান তৈরি করা যাক।
এখানে আমাদের নোডের একই স্তরে সমস্ত নোড প্রিন্ট করতে হবে অর্থাৎ রুট নোড থেকে একই দূরত্বে থাকা সমস্ত নোড। কিন্তু আমাদের সেই নোডটিকে নির্মূল করতে হবে যার নোডের মতো একই অভিভাবক রয়েছে। এর জন্য, আমরা প্রথমে নোডের স্তরটি খুঁজে বের করব এবং তারপর নোডটি এবং একই প্যারেন্ট সহ নোড ছাড়া সমস্ত নোড প্রিন্ট করব।
উদাহরণ
এখন, এই যুক্তির উপর ভিত্তি করে একটি প্রোগ্রাম তৈরি করা যাক -
#include <bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node *left, *right;
};
Node *newNode(int item){
Node *temp = new Node;
temp->data = item;
temp->left = temp->right = NULL;
return temp;
}
int levelOfNode(Node *root, Node *node, int level){
if (root == NULL)
return 0;
if (root == node)
return level;
int downlevel = levelOfNode(root->left,
node, level + 1);
if (downlevel != 0)
return downlevel;
return levelOfNode(root->right, node, level + 1);
}
void printCousin(Node* root, Node *node, int level){
if (root == NULL || level < 2)
return;
if (level == 2){
if (root->left == node || root->right == node)
return;
if (root->left)
cout << root->left->data << " ";
if (root->right)
cout << root->right->data;
}
else if (level > 2){
printCousin(root->left, node, level - 1);
printCousin(root->right, node, level - 1);
}
}
void cousinNode(Node *root, Node *node){
int level = levelOfNode(root, node, 1);
printCousin(root, node, level);
}
int main(){
Node *root = newNode(11);
root->left = newNode(15);
root->right = newNode(4);
root->left->left = newNode(3);
root->left->right = newNode(7);
root->left->right->right = newNode(9);
root->right->left = newNode(17);
root->right->right = newNode(8);
root->right->left->right = newNode(5);
cout<<”The cousin nodes are : \t”
cousinNode(root, root->right->right);
return 0;
} আউটপুট
The cousin nodes are : 3 7
