এই সমস্যায়, আমরা একটি বাইনারি গাছ দেওয়া হয়. আমাদের কাজ হল প্রদত্ত গাছের সর্বোচ্চ গভীরতা বা উচ্চতা খুঁজে বের করার জন্য একটি প্রোগ্রাম লেখা।
সমস্যাটি বোঝার জন্য একটি উদাহরণ দেওয়া যাক,
গাছের উচ্চতা 3.
একটি গাছের সর্বোচ্চ উচ্চতা খুঁজে বের করার জন্য, আমরা তার বাম এবং ডান উপবৃক্ষের উচ্চতা পরীক্ষা করব এবং উভয়ের সর্বোচ্চে একটি যোগ করব। এটি একটি পুনরাবৃত্ত প্রক্রিয়া যা এটি চালিয়ে যাবে গাছের শেষ নোডটি পাওয়া যায় এবং একটি সাব-ট্রির উচ্চতা খুঁজে পেতে ক্রমান্বয়ে যুক্ত করা হয়৷
উপরের উদাহরণ এই পদ্ধতি ব্যবহার করে সমাধান করা হয়েছে।
গাছের উচ্চতা নির্ণয় করা হচ্ছে যেমন উচ্চতা(3) =সর্বোচ্চ(উচ্চতা(5), উচ্চতা(7)) + 1।
এর জন্য, আমরা 5 এবং 7 মান সহ নোডের উচ্চতা গণনা করব।
উচ্চতা(5) =সর্বোচ্চ(উচ্চতা(1), উচ্চতা(9)) + 1 এবং
উচ্চতা(7) =1, এটির কোন উপবৃক্ষ নেই যা গঠিত হতে পারে।
একইভাবে, উচ্চতা(1) =উচ্চতা(9) =1
উচ্চতা(5) =সর্বোচ্চ(1,1) +1 =2
উচ্চতা(3) =সর্বোচ্চ(উচ্চতা(5), উচ্চতা(7)) + 1 =সর্বোচ্চ(2,1) + 1 =3।
সুতরাং উচ্চতা 3 হয়ে যায়।
সমাধান চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#include <iostream>
using namespace std;
class node {
public:
int data;
node* left;
node* right;
};
int height(node* node) {
if (node == NULL)
return 0;
else {
int lDepth = height(node->left);
int rDepth = height(node->right);
if (lDepth > rDepth)
return(lDepth + 1);
else return(rDepth + 1);
}
}
node* insertNode(int data) {
node* Node = new node();
Node->data = data;
Node->left = NULL;
Node->right = NULL;
return(Node);
}
int main() {
node *root = insertNode(4);
root->left = insertNode(5);
root->right = insertNode(0);
root->left->left = insertNode(1);
root->left->right = insertNode(9);
cout<<"The height of the given binary tree is "<<height(root);
return 0;
} আউটপুট
The height of the given binary tree is 3
