এই সমস্যায়, আমাদেরকে n আকারের একটি অ্যারে দেওয়া হয়েছে যা একটি গাছকে বোঝায়। আমাদের কাজ হল প্যারেন্ট অ্যারে দ্বারা প্রতিনিধিত্ব করা বাইনারি ট্রির উচ্চতা খুঁজে বের করা।
একটি বাইনারী সার্চ ট্রি (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
