এই সমস্যায় একটি বাইনারি সার্চ ট্রি দেওয়া আছে। আমাদের ট্রির যেসব নোডের মান বিজোড় সেগুলো প্রিন্ট করতে হবে।
বাইনারি সার্চ ট্রি হলো একটি বিশেষ ধরনের ট্রি যেটির নিচের গুণাবলী রয়েছে:
- বাম সাবট্রি সবসময় রুট নোড থেকে ছোট মান ধারণ করে।
- ডান সাবট্রি সবসময় রুট নোড থেকে বড় মান ধারণ করে।
- বাম ও ডান সাবট্রিও উপরের দুটি গুণাবলী মানতে হবে।
উদাহরণ
আউটপুট - 1 3 9
এই সমস্যাটি সমাধানের একটি সহজ পদ্ধতি হচ্ছে ট্রি ট্রাভার্স করা। ট্রাভার্সালের সময় ট্রির প্রতিটি নোডের মান চেক করা হবে। যদি নোডটি বিজোড় হয় তবে প্রিন্ট করা হবে অন্যথায় ট্রির পরবর্তী নোডে যাওয়া হবে।
প্রোগ্রামের জটিলতা নোডের সংখ্যার উপর নির্ভর করবে। সময় জটিলতা: O(n)।
বাস্তবায়ন
#include <bits/stdc++.h>
using namespace std;
struct Node {
int key;
struct Node *left, *right;
};
Node* newNode(int item) {
Node* temp = new Node;
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
Node* insertNode(Node* node, int key) {
if (node == NULL)
return newNode(key);
if (key < node->key)
node->left = insertNode(node->left, key);
else
node->right = insertNode(node->right, key);
return node;
}
void printOddNodes(Node* root) {
if (root != NULL) {
printOddNodes(root->left);
if (root->key % 2 != 0)
cout << root->key << "\t";
printOddNodes(root->right);
}
}
int main() {
Node* root = NULL;
root = insertNode(root, 6);
root = insertNode(root, 3);
root = insertNode(root, 1);
root = insertNode(root, 4);
root = insertNode(root, 9);
root = insertNode(root, 8);
root = insertNode(root, 10);
cout << "Nodes with odd values are :\n";
printOddNodes(root);
return 0;
}
আউটপুট
Nodes with odd values are : 1 3 9
