हमें एक बाइनरी ट्री इनपुट के रूप में दिया गया है। लक्ष्य उसमें मौजूद बाइनरी सर्च ट्री (BST) सबट्री की संख्या ज्ञात करना है। BST एक बाइनरी ट्री है जिसमें बायां चाइल्ड रूट से कम और दायां चाइल्ड रूट से अधिक होता है।
उदाहरण के लिए
इनपुट
मानों को इनपुट करने के बाद जो ट्री बनेगा वह नीचे दिया गया है:

आउटपुट
Count the Number of Binary Search Trees present in a Binary Tree are: 2
व्याख्या
हमें पूर्णांक मानों की एक सरणी दी गई है जिसका उपयोग बाइनरी ट्री बनाने के लिए किया जाता है और हम जांचेंगे कि क्या इसमें कोई बाइनरी सर्च ट्री मौजूद है। प्रत्येक रूट नोड एक बाइनरी सर्च ट्री को दर्शाता है इसलिए दिए गए बाइनरी ट्री में हम देख सकते हैं कि कोई अन्य बाइनरी सर्च ट्री मौजूद नहीं है इसलिए गिनती 2 है जो बाइनरी ट्री में लीफ नोड्स की कुल संख्या है।
इनपुट
मानों को इनपुट करने के बाद जो ट्री बनेगा वह नीचे दिया गया है:

आउटपुट
Count the Number of Binary Search Trees present in a Binary Tree are: 6
व्याख्या
हमें पूर्णांक मानों की एक सरणी दी गई है जिसका उपयोग बाइनरी ट्री बनाने के लिए किया जाता है और हम जांचेंगे कि क्या इसमें कोई बाइनरी सर्च ट्री मौजूद है। प्रत्येक रूट नोड एक बाइनरी सर्च ट्री को दर्शाता है इसलिए दिए गए बाइनरी ट्री में हम देख सकते हैं कि 4 लीफ नोड्स और दो सबट्री हैं जो BST बना रहे हैं इसलिए गिनती 6 है।


नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण इस प्रकार है:
इस दृष्टिकोण में हम नोड N के बाएं सबट्री में नोड के सबसे बड़े मान को ढूंढते हैं और जांचते हैं कि क्या यह N से कम है। साथ ही, हम नोड N के दाएं सबट्री में सबसे छोटे मान को ढूंढते हैं और जांचते हैं कि क्या यह N से अधिक है। यदि सही है, तो यह एक BST है। बाइनरी ट्री को बॉटम-अप तरीके से ट्रैवर्स करें और उपरोक्त शर्तों की जांच करें और BST की गिनती बढ़ाएं।
प्रत्येक नोड के नोड_डेटा में उस ट्री में मौजूद BST की संख्या, उस ट्री में अधिकतम मान, न्यूनतम मान, बूलियन ट्रू यदि वह सबट्री BST है जैसी जानकारी होती है।
फ़ंक्शन BST_present(struct tree_node* parent) parent पर रूटेड बाइनरी ट्री के अंदर मौजूद BST की संख्या ढूंढता है।
यदि parent NULL है तो { 0, min, max, true } लौटाएं जहां min INT_MIN है और max INT_MAX है।
यदि बाएं और दाएं चाइल्ड NULL हैं तो { 1, parent->data, parent->data, true } लौटाएं।
node_data Left = BST_present(parent->left); और node_data Right = BST_present(parent->right); सेट करें।
नोड n1 लें और n1.lowest = min(parent->data, (min(Left.lowest, Right.lowest))) को उसके दाएं सबट्री में सबसे कम मान के रूप में सेट करें।
n1.highest = max(parent->data, (max(Left.highest, Right.highest))); को उसके बाएं सबट्री में सबसे अधिक मान के रूप में सेट करें।
if(Left.check && Right.check && parent->data > Left.highest && parent->data < Right.lowest) ट्रू लौटाता है तो n1.check = true सेट करें क्योंकि यह एक BST है।
BST की गिनती बढ़ाएं: n1.total_bst = 1 + Left.total_bst + Right.total_bst;
अन्यथा n1.check = false सेट करें और गिनती को n1.total_bst = Left.total_bst + Right.total_bst के रूप में सेट करें।
अंत में n1 लौटाएं।
उदाहरण
#include <bits/stdc++.h> using namespace std; struct tree_node{ struct tree_node* left; struct tree_node* right; int data; tree_node(int data){ this->data = data; this->left = NULL; this->right = NULL; } }; struct node_data{ int total_bst; int highest, lowest; bool check; }; node_data BST_present(struct tree_node* parent){ if(parent == NULL){ int max = INT_MAX; int min = INT_MIN; return { 0, min, max, true }; } if(parent->left == NULL){ if(parent->right == NULL){ return { 1, parent->data, parent->data, true }; } } node_data Left = BST_present(parent->left); node_data Right = BST_present(parent->right); node_data n1; n1.lowest = min(parent->data, (min(Left.lowest, Right.lowest))); n1.highest = max(parent->data, (max(Left.highest, Right.highest))); if(Left.check && Right.check && parent->data > Left.highest && parent->data < Right.lowest){ n1.check = true; n1.total_bst = 1 + Left.total_bst + Right.total_bst; } else{ n1.check = false; n1.total_bst = Left.total_bst + Right.total_bst; } return n1; } int main(){ struct tree_node* root = new tree_node(3); root->left = new tree_node(7); root->right = new tree_node(4); root->left->left = new tree_node(5); root->right->right = new tree_node(1); root->left->left->left = new tree_node(10); cout<<"Count the Number of Binary Search Trees present in a Binary Tree are: "<<BST_present(root).total_bst; return 0; } आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्नलिखित आउटपुट उत्पन्न करेगा:
Count the Number of Binary Search Trees present in a Binary Tree are: 2