এই সমস্যায়, আমাদের একটি অ্যারে arr[] দেওয়া হয়েছে যার সাইজ n এবং যা একটি ট্রি নির্দেশ করে। আমাদের কাজ হলো পেরেন্ট অ্যারে দ্বারা প্রতিনিধিত্ব করা বাইনারি ট্রির উচ্চতা খুঁজে বের করা।
বাইনারি সার্চ ট্রি (BST) হলো এমন একটি ট্রি যেখানে সব নোড নিচের বৈশিষ্ট্য মেনে চলে:
- বাম সাব-ট্রির কী মান এর পেরেন্ট (রুট) নোডের কী মান থেকে ছোট।
- ডান সাব-ট্রির কী মান এর পেরেন্ট (রুট) নোডের কী মান থেকে বড় বা সমান।
ট্রির উচ্চতা হলো রুট নোড থেকে সবচেয়ে দূরবর্তী লিফ নোড পর্যন্ত যেতে পারা নোডের সংখ্যা।
সমাধানের পদ্ধতি
এই সমস্যার একটি সহজ সমাধান হলো পেরেন্ট অ্যারে থেকে ট্রি তৈরি করা। তারপর এই ট্রির রুট খুঁজে বের করে, লেফট এবং রাইট সাব-ট্রি için রিকার্শন করে সর্বোচ্চ উচ্চতা রিটার্ন করা।
একটি আরও কার্যকর পদ্ধতি হবে অ্যারে থেকে নোডের গভীরতা হিসাব করে সেগুলো একটি ডেপথ অ্যারেতে সংরক্ষণ করা। তারপর সেই অ্যারে থেকে সর্বোচ্চ গভীরতা রিটার্ন করা।
সমাধানটি ব্যাখ্যা করে প্রোগ্রাম
#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
