इस समस्या में, हमें एक बाइनरी सर्च ट्री दी गई है और हमें उन सभी नोड्स को प्रिंट करना है जिनके मान विषम हैं।
बाइनरी सर्च ट्री
बाइनरी सर्च ट्री एक विशेष प्रकार का ट्री है जिसमें निम्नलिखित गुण होते हैं:
- बायां सबट्री हमेशा रूट नोड से छोटे मान रखता है।
- दायां सबट्री हमेशा रूट नोड से बड़े मान रखता है।
- बाएं और दाएं दोनों सबट्री को उपरोक्त दो गुणों का पालन करना होगा।
उदाहरण
आउटपुट - 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
