একটি ট্রি দেওয়া আছে, এবং আমাদের দৈর্ঘ্য দেওয়া k-এর চেয়ে ছোট পথের লিফ নোড (leaf node) রিমুভ করতে হবে। উদাহরণস্বরূপ:
ইনপুট −
K = 4.
আউটপুট −
ব্যাখ্যা
পথগুলো ছিল: 1. A -> B -> C -> E দৈর্ঘ্য = 4 2. A -> B -> C -> F দৈর্ঘ্য = 4 3. A -> B -> D দৈর্ঘ্য = 3 4. A -> G -> H দৈর্ঘ্য = 3 5. A -> B -> I দৈর্ঘ্য = 3 এখন আপনি দেখতে পাচ্ছেন পথ ৩, ৪, ৫-এর দৈর্ঘ্য ৩ যা দেওয়া k-এর চেয়ে ছোট, তাই আমরা এই পথগুলোর লিফ নোডগুলো রিমুভ করি অর্থাৎ D, H, I। এখন পথ ৪ এবং ৫-এ H এবং I রিমুভ হলে আমরা লক্ষ্য করি G-ও এখন একটি লিফ নোড যার পথ দৈর্ঘ্য ২, তাই আমরা আবার নোড G রিমুভ করি এবং এখানেই আমাদের প্রোগ্রাম শেষ হয়।
আমরা ট্রিকে পোস্ট-অর্ডার (post-order) ফরম্যাটে ট্রাভার্স করব; তারপর, আমরা একটি রিকারসিভ ফাংশন তৈরি করব যা পথের দৈর্ঘ্য K-এর চেয়ে ছোট হলে লিফ নোডগুলো রিমুভ করবে।
সমাধানের পদ্ধতি
এই পদ্ধতিতে, আমরা পোস্ট-অর্ডার ট্রাভার্সালে ট্রাভার্স করি; এখন, আমরা রিকারসিভলি লিফ নোডগুলো রিমুভ করার চেষ্টা করি যাদের পথ দৈর্ঘ্য k-এর চেয়ে ছোট এবং এই প্রক্রিয়া চলতে থাকে।
উদাহরণ
উপরোক্ত পদ্ধতির জন্য C++ কোড
#include<bits/stdc++.h> using namespace std; struct Node{ // আমাদের নোডের কাঠামো char data; Node *left, *right; }; Node *newNode(int data){ // নতুন নোড ইনসার্ট Node *node = new Node; node->data = data; node->left = node->right = NULL; return node; } Node *trimmer(Node *root, int len, int k){ if (!root) // যদি root == NULL হয় তবে রিটার্ন return NULL; root -> left = trimmer(root -> left, len + 1, k); // লেফট ফেজ ট্রাভার্স root -> right = trimmer(root -> right, len + 1, k); // রাইট ফেজ ট্রাভার্স if (!root -> left && !root -> right && len < k){ delete root; return NULL; } return root; } Node *trim(Node *root, int k){ return trimmer(root, 1, k); } void printInorder(Node *root){ if (root){ printInorder(root->left); cout << root->data << " "; printInorder(root->right); } } int main(){ int k = 4; Node *root = newNode('A'); root->left = newNode('B'); root->right = newNode('G'); root->left->left = newNode('C'); root->left->right = newNode('D'); root->left->left->left = newNode('E'); root->left->left->right = newNode('F'); root->right->left = newNode('H'); root->right->right = newNode('I'); printInorder(root); cout << "\n"; root = trim(root, k); printInorder(root); return 0; }
আউটপুট
E C F B D A H G I E C F B A
উপরোক্ত কোডের ব্যাখ্যা
এই কোডে, আমরা একটি রিকারসিভ ফাংশন ব্যবহার করছি যা আমাদের ট্রি ট্রাভার্স করে এবং লেফট ও রাইট সাবট্রির স্ট্যাটস রাখে। এখন যখন আমরা একটি লিফ নোডে পৌঁছাই, তবে আমরা সেটি পর্যন্ত পথের দৈর্ঘ্য চেক করি। যদি পথের দৈর্ঘ্য কম হয়, তবে আমরা এই নোডটি ডিলিট করি, এবং NULL রিটার্ন করি; অন্যথায় কোড চালিয়ে যায়।
উপসংহার
এই টিউটোরিয়ালে, আমরা রিকারসন ব্যবহার করে রুট-টু-লিফ পথের দৈর্ঘ্য K-এর চেয়ে ছোট হলে নোড রিমুভ করার সমস্যা সমাধান করেছি। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং রিকারসন শিখেছি এবং সম্পূর্ণ পদ্ধতি जिससे আমরা সমাধান করেছি। একই প্রোগ্রামটি C, Java, Python এবং অন্যান্য ভাষায়ও লিখা যায়। আশা করি আপনি এই টিউটোরিয়ালটিকে উপকারী পাবেন।
