प्रीऑर्डर ट्रैवर्सल का उपयोग करके BST में रूट से छोटे तत्वों की संख्या ज्ञात करना C++ में

आपको प्रीऑर्डर ट्रैवर्सल का परिणाम दिया गया है। आपको उन तत्वों की संख्या ज्ञात करनी है जो रूट से छोटे हैं।

प्रीऑर्डर ट्रैवर्सल में पहला तत्व BST का रूट होता है। आइए एक उदाहरण देखते हैं।

इनपुट

preorder_result = [5, 4, 2, 1, 7, 6, 8, 9]

आउटपुट

3

रूट से छोटे तीन तत्व हैं। रूट 5 है।

एल्गोरिदम

• प्रीऑर्डर परिणाम को एक सरणी में आरंभ करें।
• पहला तत्व यानी BST का रूट एक वेरिएबल में स्टोर करें।
• एक लूप लिखें जो प्रीऑर्डर परिणाम के दूसरे तत्व से पुनरावृति करता है।
• प्रत्येक तत्व की तुलना रूट से करें।
• यदि वर्तमान तत्व रूट से छोटा है, तो काउंट बढ़ाएं।
• काउंट वापस करें।

कार्यान्वयन

निम्नलिखित C++ में उपरोक्त एल्गोरिदम का कार्यान्वयन है:

#include <bits/stdc++.h> 
using namespace std; 

int getElementsCount(int arr[], int n) { 
    if (n < 0) { 
        return 0; 
    } 
    int i, root = arr[0], count = 0; 
    for(i = 1; i < n; i++) { 
        if(arr[i] < root) { 
            count += 1; 
        } 
    } 
    return count; 
} 

int main() { 
    int preorder[] = {5, 4, 2, 1, 7, 6, 8, 9}; 
    int n = 8; 
    cout << getElementsCount(preorder, n) << endl; 
    return 0; 
}

आउटपुट

यदि आप उपरोक्त कोड चलाते हैं, तो आपको निम्नलिखित परिणाम मिलेगा।

3