इस समस्या में हमें एक बाइनरी ट्री दिया जाता है। और हमें जड़ से लेकर पेड़ के पत्ते तक के सभी रास्तों को प्रिंट करना होता है। साथ ही, नोड्स की सापेक्ष स्थिति दिखाने के लिए अंडरस्कोर “_” जोड़ें।
आइए विषय को बेहतर ढंग से समझने के लिए एक उदाहरण लेते हैं -
इनपुट -
आउटपुट -
_ _ 3 _ 9 1 _3 9 _7 3 _ 4 _ _ 2 3 9 4 1 7 6 2 3 _ 4 6
इस समस्या को हल करने के लिए, हम पेड़ के तत्वों के लंबवत क्रम की अवधारणा का उपयोग करेंगे।
इसके आधार पर, हम रूट से लीफ तक के पाथ को प्रिंट करेंगे।
एल्गोरिदम
Step 1: Traverse the binary tree using preorder traversal. And on traversal calculate the horizontal distance based on the order. The horizontal distance of root is 0 and processed as the above diagram. Step 2: And on traversing to the leaf node, print the path with an underscore “_” at the end.
उदाहरण
#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