এই সমস্যায় একটি বাইনারি ট্রি দেওয়া আছে। আমাদের বাইনারি ট্রির সব লিফ নোড ডান থেকে বাম প্রিন্ট করতে হবে।
উদাহরণ
ইনপুট -
আউটপুট - 7 4 1
এই সমস্যাটি সমাধানের জন্য বাইনারি ট্রি ট্রাভার্স করতে হবে। এই ট্রাভার্সাল দুটি পদ্ধতিতে করা যায় -
প্রি-অর্ডার ট্রাভার্সাল - এই ট্রাভার্সাল রিকার্শন ব্যবহার করে। এখানে রুট, তারপর বাম এবং তারপর ডান সাবট্রি ট্রাভার্স করা হবে। যদি লিফ নোড পাওয়া যায় তবে প্রিন্ট করা হবে, অন্যথায় নোডের চাইল্ডগুলো এক্সপ্লোর করা হবে।
বাস্তবায়ন (প্রি-অর্ডার)
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
Node* insertNode(int data) {
Node* temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
void findLeafNode(Node* root) {
if (!root)
return;
if (!root->left && !root->right) {
cout << root->data << "\t";
return;
}
if (root->right)
findLeafNode(root->right);
if (root->left)
findLeafNode(root->left);
}
int main() {
Node* root = insertNode(21);
root->left = insertNode(5);
root->right = insertNode(11);
root->left->left = insertNode(8);
root->left->right = insertNode(98);
root->right->left = insertNode(2);
root->right->right = insertNode(8);
cout << "Leaf nodes of the tree from right to left are:\n";
findLeafNode(root);
return 0;
}
আউটপুট
Leaf nodes of the tree from right to left are : 18 2 98 8
পোস্ট-অর্ডার ট্রাভার্সাল - এই ট্রাভার্সাল লিফ নোড খুঁজে বের করতে ইটারেশন ব্যবহার করে। আমরা একটি স্ট্যাক ব্যবহার করব ডেটা সংরক্ষণের জন্য এবং ট্রি পোস্ট-অর্ডার পদ্ধতিতে (প্রথম ডান সাবট্রি তারপর বাম সাবট্রি এবং তারপর রুট) ট্রাভার্স করব এবং লিফ নোড প্রিন্ট করব।
বাস্তবায়ন (পোস্ট-অর্ডার)
#include<bits/stdc++.h>
using namespace std;
struct Node {
Node* left;
Node* right;
int data;
};
Node* insertNode(int key) {
Node* node = new Node();
node->left = node->right = NULL;
node->data = key;
return node;
}
void findLeafNode(Node* tree) {
stack<Node*> treeStack;
while (1) {
if (tree) {
treeStack.push(tree);
tree = tree->right;
} else {
if (treeStack.empty())
break;
else {
if (treeStack.top()->left == NULL) {
tree = treeStack.top();
treeStack.pop();
if (tree->right == NULL)
cout << tree->data << "\t";
}
while (tree == treeStack.top()->left) {
tree = treeStack.top();
treeStack.pop();
if (treeStack.empty())
break;
}
if (!treeStack.empty())
tree = treeStack.top()->left;
else
tree = NULL;
}
}
}
}
int main() {
Node* root = insertNode(21);
root->left = insertNode(5);
root->right = insertNode(11);
root->left->left = insertNode(8);
root->left->right = insertNode(98);
root->right->left = insertNode(2);
root->right->right = insertNode(18);
cout << "Leaf nodes of the tree from right to left are:\n";
findLeafNode(root);
return 0;
}
আউটপুট
Leaf nodes of the tree from right to left are : 18 2 98 8
