বাইনারি ট্রি দেওয়া থাকলে প্রোগ্রামটি রুট থেকে লিফ পর্যন্ত অনেক পথের মধ্যে সবচেয়ে ছোটো পথটি বের করবে।
যেহেতু আমরা ট্রি বাম থেকে ডান দিকে ট্রাভার্স করি, তাই যদি রুট থেকে লিফ পর্যন্ত একাধিক ছোটো পথ থাকে তবে প্রোগ্রামটি বাম পাশের প্রথম ট্রাভার্স করা ছোটো পথটি প্রিন্ট করবে।
আমরা একটি কিউ ব্যবহার করতে পারি যা লেভেল অর্ডার ট্রাভার্সাল ব্যবহার করে প্রতিটি লেভেল ট্রাভার্স করবে এবং সবচেয়ে কম লেভেল বিশিষ্ট পথটি প্রিন্ট করবে কারণ সেটিই রুট থেকে লিফ পর্যন্ত সবচেয়ে ছোটো পথ।
উপরের ট্রিতে, রুট থেকে লিফ পর্যন্ত একাধিক পথ রয়েছে −
10 -> 3 (এটি সবচেয়ে ছোটো পথ) 10 -> 211 -> 100 10 -> 211 -> 146
উদাহরণ
ইনপুট: 10 3 211 100 146 আউটপুট: 10 3
অ্যালগরিদম
Step 1 → create a structure of a node as struct node struct node *left, *right int data End Step 2 → function to create a node node* newnode(int data) node *temp = new node temp->data = data temp->left = temp->right= NULL return temp Step 3 → create function for calculating path void path(int data, unordered_map <int,int> prnt) IF prnt[data] = data Return End path(prnt[data], prnt) print prnt[data] step 4 → function for finding out the left path void left(Node* root) create STL queue<Node*> que que.push(root) int leaf = -1 Node* temp = NULL Create STL unordered_map<int, int> prnt prnt[root->data] = root->data Loop While !que.empty() temp = que.front() que.pop() IF !temp->left && !temp->right leaf = temp->data break End Else IF temp->left que.push(temp->left) prnt[temp->left->data] = temp->data End IF temp->right que.push(temp->right) prnt[temp->right->data] = temp->data End End End path(leaf, prnt) print leaf Step 5 → In main() Create tree using Node* root = newnode(90) root->left = newnode(21) call left(root) stop
উদাহরণ
#include <bits/stdc++.h> using namespace std; // structure of a node struct Node { struct Node *left,*right; int data; }; //function to create a new node Node* newnode(int data){ Node* temp = new Node; temp->data = data; temp->left = NULL; temp->right = NULL; return temp; } //function to set a path void path(int data, unordered_map <int,int> prnt) { if (prnt[data] == data) return; path(prnt[data], prnt); cout << prnt[data] << " "; } //function for a leaf path void left(Node* root) { queue<Node*> que; que.push(root); int leaf = -1; Node* temp = NULL; unordered_map<int, int> prnt; prnt[root->data] = root->data; while (!que.empty()){ temp = que.front(); que.pop(); if (!temp->left && !temp->right{ leaf = temp->data; break; } else { if (temp->left){ que.push(temp->left); prnt[temp->left->data] = temp->data; } if (temp->right){ que.push(temp->right); prnt[temp->right->data] = temp->data; } } } path(leaf, prnt); cout << leaf << " "; } int main(){ Node* root = newnode(90); root->left = newnode(21); root->right = newnode(32); root->left->left = newnode(45); root->right->left = newnode(52); root->right->right = newnode(27); root->left->left->left = newnode(109); root->left->left->right = newnode(101); root->right->right->left = newnode(78); left(root); return 0; }
আউটপুট
যদি আমরা উপরের প্রোগ্রামটি রান করি তবে এটি নিচের আউটপুট জেনারেট করবে
90 32 52
