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