একটি ব্যালেন্সড বাইনারি সার্চ ট্রি দেওয়া আছে। is_valid_triplet() ফাংশন লিখুন যা true ফেরত দেবে যদি যোগফল শূন্য হওয়া ট্রিপলেট থাকে, নয় তবে false। কনস্ট্রেইন্ট: টাইম O(n²), এক্সট্রা স্পেস O(log n)।
ইনপুট ট্রি (চিত্র): -15, 7, 8 ট্রিপলেটের যোগফল ০। আউটপুট: True।
সমাধানের ধাপসমূহ
- BST কে ডাবলি লিংকড লিস্ট-এ কনভার্ট করুন (ইন-অর্ডার ট্রাভার্সাল)।
- ডাবলি লিস্ট-এ টু-পয়েন্টার টেকনিক দিয়ে দুটি সংখ্যার যোগফল নির্দিষ্ট মান হয় কিনা চেক করুন।
- প্রতিটি নেগেটিভ নোডের জন্য বাকি লিস্টে তার ঋণাত্মক মান এর সমান যোগফল দিয়ে জোড়া আছে কিনা চেক করুন।
উদাহরণ (C++ কোড)
#include <bits/stdc++.h>
using namespace std;
class TreeNode {
public:
int key;
TreeNode *left, *right;
TreeNode() : key(0), left(NULL), right(NULL) {}
TreeNode(int x) : key(x), left(NULL), right(NULL) {}
};
void bst_to_doubli_list(TreeNode* root, TreeNode** head, TreeNode** tail) {
if (root == NULL) return;
if (root->left) bst_to_doubli_list(root->left, head, tail);
root->left = *tail;
if (*tail) (*tail)->right = root;
else *head = root;
*tail = root;
if (root->right) bst_to_doubli_list(root->right, head, tail);
}
bool is_in_double_list(TreeNode* head, TreeNode* tail, int sum) {
while (head != tail) {
int current = head->key + tail->key;
if (current == sum) return true;
else if (current > sum) tail = tail->left;
else head = head->right;
}
return false;
}
bool is_valid_triplet(TreeNode *root) {
if (root == NULL) return false;
TreeNode* head = NULL; TreeNode* tail = NULL;
bst_to_doubli_list(root, &head, &tail);
while ((head->right != tail) && (head->key < 0)) {
if (is_in_double_list(head->right, tail, -1*head->key)) return true;
else head = head->right;
}
return false;
}
TreeNode* insert(TreeNode* root, int key) {
if (root == NULL) return new TreeNode(key);
if (root->key > key) root->left = insert(root->left, key);
else root->right = insert(root->right, key);
return root;
}
int main() {
TreeNode* root = NULL;
root = insert(root, 7);
root = insert(root, -15);
root = insert(root, 15);
root = insert(root, -7);
root = insert(root, 14);
root = insert(root, 16);
root = insert(root, 8);
cout << is_valid_triplet(root);
}
ইনপুট
7, -15, 15, -7, 14, 16, 8
আউটপুট
1 (True)
