আমাদের একটি বাইনারি ট্রি দেওয়া আছে যাতে ডISTINCT নোড আছে এবং সেই বাইনারি ট্রির দুটি নোড দেওয়া আছে যাদের পথ বাইনারি ট্রিতে প্রিন্ট করতে হবে।
উদাহরণস্বরূপ − আমরা নোড 140 থেকে 211 পর্যন্ত পথ প্রিন্ট করতে চাই তাহলে আউটপুট হবে −
Output: 140->3->10->211
আইডিয়া হলো রুট নোড থেকে দুটি নোড পর্যন্ত পথ খুঁজে বের করা এবং সেগুলো দুটি আলাদা ভেক্টর বা অ্যারেতে সংরক্ষণ করা, বলুন path1 এবং path2।
এখন, দুটি ভিন্ন কেস ওঠে −
- যদি দুটি নোড রুট নোডের ভিন্ন সাবট্রিয়ে থাকে − যখন দুটি নোড ভিন্ন সাবট্রিয়ে থাকে যেমন একটি লेफটে এবং অন্যটি রাইটে। এই কেসে, স্পষ্ট যে রুট নোড node1 থেকে node2 পর্যন্ত পথের মাঝপথে থাকবে। তাই path1 রিভার্স অর্ডারে প্রিন্ট করুন এবং তারপর path2।
যদি নোডগুলো একই সাবট্রিতে থাকে − যখন দুটি নোড একই সাবট্রিতে থাকে যা লেফট সাবট্রি বা রাইট সাবট্রি যেকোনো একটা হতে পারে। এই কেসে, আপনাকে লক্ষ্য করতে হবে রুট থেকে দুটি নোড পর্যন্ত পথে একটি ইন্টারসেকশন পয়েন্ট থাকবে जिसके আগে রুট নোড থেকে দুটি নোডের জন্য পথ কমন থাকবে। আমাদের সেই ইন্টারসেকশন পয়েন্ট খুঁজে বের করতে হবে এবং উপরের কেসের মতো সেখান থেকে নোডগুলো প্রিন্ট করতে হবে।
অ্যালগরিদম
START STEP 1→ DEFINE A struct Node WITH int data AND Node *left, *right; STEP 2→ DEFINE A TREE STRUCTURE struct Node* tree(int data) FUNCTION bool path(Node* root, vector& arr, int x) STEP 1→ IF root IS NULL RETURN false END IF STEP 2→ arr.push_back(root->data) IF root->data == x THEN RETURN true END IF STEP 3→ IF path(root->left, arr, x) || path(root->right, arr, x) THEN, RETURN true STEP 4→ arr.pop_back() return false END FUNCTION FUNCTION void printPath(Node* root, int n1, int n2) STEP 1→ DEFINE A vector<int> path1 STEP 2→ DEFINE A vector<int> path2 STEP 3→ CALL FUNCTION path(root, path1, n1) STEP 4→ CALL FUNCTION path(root, path2, n2) STEP 5→ DEFINE AND SET intersection = -1, i = 0, j = 0 STEP 6→ LOOP WHILE i != path1.size() || j != path2.size() IF i == j && path1[i] == path2[j] INCREMENT i BY 1 INCREMENT j BY 1 ELSE SET intersection = j - 1 BREAK; END IF END WHILE STEP 7→ LOOP FOR i = path1.size() – 1 AND i > intersection AND i-- PRINT path1[i] END FOR STEP 8→ LOOP FOR i = intersection AND i < path2.size() AND i++ PRINT path2[i] END FOR
উদাহরণ
#include <bits/stdc++.h> using namespace std; // structure of a node of binary tree struct Node { int data; Node *left, *right; }; struct Node* tree(int data){ struct Node* newNode = new Node; newNode->data = data; newNode->left = newNode->right = NULL; return newNode; } bool path(Node* root, vector<int>& arr, int x){ if (!root) return false; // push the node's value in 'arr' arr.push_back(root->data); // if it is the required node // return true if (root->data == x) return true; if (path(root->left, arr, x) || path(root->right, arr, x)) return true; arr.pop_back(); return false; } // Function to print the path between // any two nodes in a binary tree void printPath(Node* root, int n1, int n2){ // vector to store the path vector<int> path1; vector<int> path2; path(root, path1, n1); path(root, path2, n2); int intersection = -1; int i = 0, j = 0; while (i != path1.size() || j != path2.size()) { if (i == j && path1[i] == path2[j]) { i++; j++; } else { intersection = j - 1; break; } } // Print the required path for (int i = path1.size() - 1; i > intersection; i--) cout << path1[i] << " "; for (int i = intersection; i < path2.size(); i++) cout << path2[i] << " "; } int main(){ // binary tree formation struct Node* root = tree(1); root->left = tree(2); root->left->left = tree(4); root->left->left->left = tree(6); root->left->right = tree(5); root->left->right->left = tree(7); root->left->right->right = tree(8); root->right = tree(3); root->right->left = tree(9); root->right->right = tree(10); int node1 = 5; int node2 = 9; printPath(root, node1, node2); return 0; }
আউটপুট
এই প্রোগ্রাম আউটপুট প্রিন্ট করবে −
5 2 1 3 9
