এই টিউটোরিয়ালে বাইনারি ট্রিতে প্রথম সবচেয়ে ছোট রুট-টু-লিফ (root-to-leaf) পাথ প্রিন্ট করার প্রোগ্রাম আলোচনা করা হবে।
এখানে একটি বাইনারি ট্রি দেওয়া থাকবে যার নোডগুলোর মান ভিন্ন (distinct)। রুট নোড থেকে লিফ নোড পর্যন্ত সবচেয়ে ছোট পাথ বের করতে হবে।
সমাধান: কিউ (queue) ব্যবহার করে লেভেল অর্ডার ট্রাভার্সাল (level order traversal) করা এবং শর্টেস্ট পাথের নোডগুলো সংরক্ষণ করা। চূড়ান্ত লেভেলের বামপাশের নোড পাওয়া গেলে কিউ থেকে মানগুলো রিট্রিভ (retrieve) করে শর্টেস্ট পাথ প্রিন্ট করা।
উদাহরণ
#include <bits/stdc++.h> using namespace std; struct Node{ struct Node* left; struct Node* right; int data; }; struct Node* create_node(int data){ struct Node* temp = new Node; temp->data = data; temp->left = NULL; temp->right = NULL; return temp; } void print_spath(int Data, unordered_map parent){ if (parent[Data] == Data) return; print_spath(parent[Data], parent); cout << parent[Data] << " "; } void leftmost_path(struct Node* root){ queue q; q.push(root); int LeafData = -1; struct Node* temp = NULL; unordered_map parent; parent[root->data] = root->data; while (!q.empty()){ temp = q.front(); q.pop(); if (!temp->left && !temp->right){ LeafData = temp->data; break; } else{ if (temp->left){ q.push(temp->left); parent[temp->left->data] = temp->data; } if (temp->right) { q.push(temp->right); parent[temp->right->data] = temp->data; } } } print_spath(LeafData, parent); cout << LeafData << " "; } int main(){ struct Node* root = create_node(21); root->left = create_node(24); root->right = create_node(35); root->left->left = create_node(44); root->right->left = create_node(53); root->right->right = create_node(71); root->left->left->left = create_node(110); root->left->left->right = create_node(91); root->right->right->left = create_node(85); leftmost_path(root); return 0; } আউটপুট
21 35 53
