इस समस्या में, हमें आकार 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
