सी ++ में पैरेंट सरणी द्वारा दर्शाए गए बाइनरी ट्री की ऊंचाई पाएं

इस समस्या में, हमें n आकार का एक सरणी arr[] दिया जाता है जो एक पेड़ को दर्शाता है। हमारा काम है पैरेंट ऐरे द्वारा दर्शाए गए बाइनरी ट्री की ऊंचाई का पता लगाना।

एक बाइनरी सर्च ट्री (BST) एक पेड़ है जिसमें सभी नोड्स नीचे बताए गए गुणों का पालन करते हैं -

• बाएं उप-वृक्ष की कुंजी का मान उसके पैरेंट (रूट) नोड की कुंजी के मान से कम है।
• राइट सबट्री की कुंजी का मान उसके पैरेंट (रूट) नोड की कुंजी के मान से अधिक या उसके बराबर है।

पेड़ की ऊंचाई रूट नोड से सबसे दूर लीफ नोड तक जाने पर ट्रैवर्स किए गए नोड्स की संख्या है।

समाधान दृष्टिकोण:

समस्या का एक सरल समाधान पैरेंट एरे से एक ट्री बनाना है। इस पेड़ की जड़ का पता लगाना और पाए गए इंडेक्स के लिए बार-बार बाएँ और दाएँ सबट्री बनाना और फिर अधिकतम ऊँचाई लौटाना।

एक अधिक कुशल विधि सरणी और स्टोर से नोड्स की गहराई की गणना करेगी और फिर इसे गहराई से सरणी में संग्रहीत करेगी। इस सरणी से अधिकतम गहराई लौटाएं।

हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,

उदाहरण

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

void findAllDepths(int arr[], int i, int nodeDepth[]) {
   
   if (nodeDepth[i])
      return;
   if (arr[i] == -1) {
     
      nodeDepth[i] = 1;
      return;
   }
   if (nodeDepth[arr[i]] == 0)
      findAllDepths(arr, arr[i], nodeDepth);
   nodeDepth[i] = nodeDepth[arr[i]] + 1;
}

int findMaxHeightBT(int arr[], int n) {

   int nodeDepth[n];
   for (int i = 0; i < n; i++)
      nodeDepth[i] = 0;
   for (int i = 0; i < n; i++)
      findAllDepths(arr, i, nodeDepth);
   int maxHeight = nodeDepth[0];
   for (int i=1; i<n; i++)
      if (maxHeight < nodeDepth[i])
         maxHeight = nodeDepth[i];
   return maxHeight;
}

int main() {
   
   int arr[] = {-1, 0, 0, 1, 1};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout<<"The maximum height of binary Tree is "<<findMaxHeightBT(arr, n);
   return 0;
}

आउटपुट -

The maximum height of binary Tree is 3