এই সমস্যায়, আমাদের একটি বাইনারি ট্রি দেওয়া আছে যেখানে প্রতিটি নোডে একটি মান রয়েছে। আমাদের কাজ হলো দুটি লিফ নোডের মধ্যে সর্বোচ্চ পথ যোগফল বের করার একটি প্রোগ্রাম তৈরি করা।
এখানে আমাদের একটি লিফ নোড থেকে অন্য লিফ নোডে এমন পথ খুঁজে বের করতে হবে যা সর্বোচ্চ মান যোগফল দেবে। এই সর্বোচ্চ যোগফল দেয় পথটি রুট নোডকে অন্তর্ভুক্ত করতে পারে বা নাও পারে।
বাইনারি ট্রি হলো একটি ট্রি ডেটা স্ট্রাকচার যেখানে প্রতিটি নোডে সর্বোচ্চ দুটি চাইল্ড নোড থাকতে পারে। এগুলোকে লেফ্ট চাইল্ড এবং রাইট চাইল্ড বলা হয়।
উদাহরণ −
সমস্যা বুঝতে নিচের উদাহরণটি দেখুন −
ইনপুট − //বাইনারি ট্রি…
আউটপুট − 24
ব্যাখ্যা − লিফ নোড ২ থেকে ৯ পর্যন্ত পথটি সর্বোচ্চ যোগফল দেবে যা হলো (2 + 5 + 6 -2 + 4 + 9 ) = 24
এই সমস্যা সমাধানের জন্য আমরা ট্রি ট্রাভার্সাল করব এবং বর্তমান নোডের জন্য বাম সাব-ট্রি/ডান সাব-ট্রির সর্বোচ্চ যোগফল সংরক্ষণ করব। সাথে সাথে আমরা দুটি লিফ নোডের মধ্যে সর্বোচ্চ পথও বের করব।
প্রতিটি নোডের জন্য, আমরা এর সাব-ট্রিগুলোর সর্বোচ্চ সম্ভাব্য লিফ-টু-লিফ পথ বের করব। তারপর তা গ্লোবাল সর্বোচ্চ পথের সাথে তুলনা করব এবং দুটির মধ্যে সর্বোচ্চ মানটি গ্লোবাল সর্বোচ্চ পথ যোগফলে সংরক্ষণ করব।
উদাহরণ থেকে সমাধান বুঝতে নিচের বিবরণটি দেখুন −
গ্লোবাল সর্বোচ্চ যোগফল = 6 (পথ 2→5→-1 এর জন্য)
এখন আমরা 6 কে রুট নোড হিসেবে বিবেচনা করব।
বাম সাব-ট্রিতে −
লিফ নোড পর্যন্ত পথের যোগফল ৭ এবং ৪।
সর্বোচ্চ হলো ৭ (পথ 5→2-এর জন্য)।
ডান সাব-ট্রিতে −
লিফ নোড পর্যন্ত পথের যোগফল ৫ (পথ 1→-3→7) যা একটি সম্ভাব্য পথ।
এখন লিফ নোডের মধ্যে পথের যোগফল −
বাম সাব-ট্রিতে লিফ-টু-রুট(৬) সর্বোচ্চ যোগফল + রুট + ডান সাব-ট্রিতে লিফ-টু-রুট(৬) সর্বোচ্চ যোগফল = 7 + 6 + 5 = 18।
গ্লোবাল সর্বোচ্চ পথ যোগফল(৬) এর সাথে তুলনা করলে, নতুন গ্লোবাল সর্বোচ্চ পথ যোগফল = 18।
উদাহরণ
দুটি লিফ নোডের মধ্যে সর্বোচ্চ পথ যোগফল বের করার প্রোগ্রাম −
#include <bits/stdc++.h> using namespace std; struct Node{ int data; struct Node* left, *right; }; struct Node* insertNode(int data){ struct Node* node = new(struct Node); node->data = data; node->left = node->right = NULL; return (node); } int max(int a, int b) { return (a >= b)? a: b; } int maxPathSumLeaf(struct Node *root, int &maxSum){ if (root==NULL) return 0; if (!root->left && !root->right) return root->data; int leftSubTree = maxPathSumLeaf(root->left, maxSum); int rightSubTree = maxPathSumLeaf(root->right, maxSum); if (root->left && root->right){ maxSum = max(maxSum, leftSubTree + rightSubTree + root->data); return max(leftSubTree, rightSubTree) + root->data; } return (!root->left)? rightSubTree + root->data: leftSubTree + root->data; } int main(){ struct Node *root = insertNode(-2); root->left = insertNode(6); root->right = insertNode(4); root->left->left = insertNode(5); root->left->right = insertNode(1); root->left->left->left = insertNode(2); root->left->left->right = insertNode(-1); root->left->right->left = insertNode(-3); root->left->right->left->left = insertNode(7); root->right->left = insertNode(9); root->right->right = insertNode(3); int maxSum = INT_MIN; maxPathSumLeaf(root, maxSum); cout<<"Max pathSum of between two leaf nodes for the given binary tree is "<<maxSum; return 0; }আউটপুট
Max pathSum of between two leaf nodes for the given binary tree is 24
