এই সমস্যায়, আমাদেরকে একটি বাইনারি ট্রি এবং একটি যোগফল S দেওয়া হয়েছে। এবং আমাদেরকে গাছের যেকোন নোডের রুট থেকে শুরু করে পথ খুঁজে বের করতে হবে, যা প্রদত্ত যোগফলের সমান দেয়।
ইনপুট
Sum = 14 Output : path : 4 10 4 3 7
এই সমস্যার সমাধান খুঁজতে, আমাদের বাইনারি গাছের প্রি-অর্ডার ট্রাভার্সাল খুঁজে বের করতে হবে। এবং তারপরে সেই পথটি সন্ধান করুন যা প্রদত্ত যোগফলের সাথে যোগ করে।
উদাহরণ
#include<bits/stdc++.h>
using namespace std;
struct Node{
int key;
struct Node *left, *right;
};
Node* insertNode(int key){
Node* temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return (temp);
}
void printPathsUtilSum(Node* curr_node, int sum, int
sum_so_far, vector<int> &path){
if (curr_node == NULL)
return;
sum_so_far += curr_node->key;
path.push_back(curr_node->key);
if (sum_so_far == sum ){
for (int i=0; i<path.size(); i++)
cout<<path[i]<<"\t";
cout<<endl;
}
if (curr_node->left != NULL)
printPathsUtilSum(curr_node->left, sum,
sum_so_far, path);
if (curr_node->right != NULL)
printPathsUtilSum(curr_node->right, sum,
sum_so_far, path);
path.pop_back();
}
void pathWithSum(Node *root, int sum){
vector<int> path;
printPathsUtilSum(root, sum, 0, path);
}
int main (){
Node *root = insertNode(4);
root->left = insertNode(10);
root->right = insertNode(3);
root->right->left = insertNode(7);
root->right->right = insertNode(1);
root->left->left = insertNode(8);
root->left->right = insertNode(6);
int sum = 14;
cout<<"Paths with the given sum are : "<<endl;
pathWithSum(root, sum);
return 0;
} আউটপুট
প্রদত্ত যোগফল সহ পাথগুলি হল −
4 10 4 3 7
