এই সমস্যায়, একটি বাইনারি ট্রি দেওয়া থাকে। এবং আমাদের ট্রির রুট থেকে লিফ পর্যন্ত সব পথ প্রিন্ট করতে হবে। সাথে সাথে আন্ডারস্কোর "_" ব্যবহার করে নোডগুলোর আপেক্ষিক অবস্থান দেখাতে হবে।
উদাহরণ দিয়ে বুঝি:
ইনপুট:
আউটপুট:
_ _ 3 _ 9 1 _3 9 _7 3 _ 4 _ _ 2 3 9 4 1 7 6 2 3 _ 4 6
এই সমস্যাটি সমাধান করতে, আমরা ট্রির এলিমেন্টের ভার্টিক্যাল অর্ডার কনসেপ্ট ব্যবহার করব।
এই ভিত্তিতে, আমরা রুট থেকে লিফ পর্যন্ত পথ প্রিন্ট করব।
অ্যালগরিদম
ধাপ ১: প্রি-অর্ডার ট্রাভার্সাল ব্যবহার করে বাইনারি ট্রি ট্রাভার্স করুন। এবং ট্রাভার্সালের সময় হরিজেন্টাল ডিস্ট্যান্স ক্যালকুলেট করুন অর্ডার অনুযায়ী। রুটের হরিজেন্টাল ডিস্ট্যান্স ০ এবং উপরের ডায়াগ্রাম অনুযায়ী প্রসেস করা হবে। ধাপ ২: এবং লিফ নোডে ট্রাভার্স করার সময়, পথটি আন্ডারস্কোর "_" সহ প্রিন্ট করুন।
C++ উদাহরণ
#include<bits/stdc++.h> using namespace std; #define MAX_PATH_SIZE 1000 struct Node{ char data; Node *left, *right; }; Node * newNode(char data){ struct Node *temp = new Node; temp->data = data; temp->left = temp->right = NULL; return temp; } struct PATH{ int horizontalDistance; char key; }; void printPath(vector < PATH > path, int size){ int minimumhorizontalDistance = INT_MAX; PATH p; for (int it=0; it<size; it++){ p = path[it]; minimumhorizontalDistance = min(minimumhorizontalDistance, p.horizontalDistance); } for (int it=0; it < size; it++){ p = path[it]; int noOfUnderScores = abs(p.horizontalDistance -minimumhorizontalDistance); for (int i = 0; i < noOfUnderScores; i++) cout<<"_ "; cout<<p.key<<endl; } cout<<"\nNext Path\n"; } void printAllRtLPaths(Node *root, vector < PATH > &AllPath, int horizontalDistance, int order ){ if(root == NULL) return; if (root->left == NULL && root->right == NULL){ AllPath[order] = (PATH { horizontalDistance, root->data }); printPath(AllPath, order+1); return; } AllPath[order] = (PATH { horizontalDistance, root->data }); printAllRtLPaths(root->left, AllPath, horizontalDistance-1, order+1); printAllRtLPaths(root->right, AllPath, horizontalDistance+1, order+1); } void printRootToLeafPath(Node *root){ if (root == NULL) return; vector<PATH> Allpaths(MAX_PATH_SIZE); printAllRtLPaths(root, Allpaths, 0, 0); } int main(){ Node *root = newNode('3'); root->left = newNode('9'); root->right = newNode('4'); root->left->left = newNode('1'); root->left->right = newNode('7'); root->right->left = newNode('6'); root->right->right = newNode('2'); printRootToLeafPath(root); return 0; }আউটপুট
_ _ 3 _ 9 1 Next Path _ 3 9 _ 7 Next Path 3 _ 4 6 Next Path 3 _ 4 _ _ 2
