একটি বাইনারি সার্চ ট্রি (BST) এর জন্য একটি ইটারেটর ডিজাইন করতে হবে যাতে next() এবং hasNext() মেথড দুটি থাকে। next() ছোট থেকে বড় ক্রমে পরবর্তী উপাদান ফেরত দেবে, hasNext() বলবে আর উপাদান আছে কিনা।
উদাহরণ
BST: [7, 3, 15, null, null, 9, 20]
ফাংশন কল: next(), next(), hasNext(), next(), hasNext(), next(), hasNext(), next(), hasNext()
আউটপুট: [3, 7, true, 9, true, 15, true, 20, false]
স্ট্যাক ভিত্তিক সমাধান
- কনস্ট্রাক্টরে রুট থেকে সব বাম নোডগুলো স্ট্যাকে পুশ করুন
next(): স্ট্যাক থেকে টপ পপ করুন, তার ডান চাইল্ড থাকলে তার বাম শাখা স্ট্যাকে পুশ করুনhasNext(): স্ট্যাক খালি কিনা চেক করুন
C++ প্রোগ্রাম উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class TreeNode {
public:
int val;
TreeNode *left, *right;
TreeNode(int data) { val = data; left = right = NULL; }
};
class BSTIterator {
public:
stack<TreeNode*> st;
void fillStack(TreeNode* node) {
while (node && node->val != 0) {
st.push(node);
node = node->left;
}
}
BSTIterator(TreeNode* root) { fillStack(root); }
int next() {
TreeNode* curr = st.top(); st.pop();
if (curr->right && curr->right->val != 0)
fillStack(curr->right);
return curr->val;
}
bool hasNext() { return !st.empty(); }
};
int main() {
// ট্রি তৈরি করার কোড এখানে সংক্ষিপ্ত করা হয়েছে
// BSTIterator ob(root);
// ob.next(), ob.hasNext() ইত্যাদি কল করুন
return 0;
}
নমুনা আউটপুট
Next: 3 Next: 7 1 Next: 9 1 Next: 15 1 Next: 20 0
