এই সমস্যায়, আমাদের একটি বাইনারি ট্রি দেওয়া আছে। আমাদের কাজ হল দেওয়া ট্রির ম্যাক্সিমাম ডেপথ বা হাইট বের করার একটি প্রোগ্রাম লিখা।
একটি উদাহরণ দিয়ে সমস্যাটি বুঝতে পারি,
ট্রির হাইট ৩।
একটি ট্রির ম্যাক্সিমাম হাইট বের করতে, আমরা এর লেফট এবং রাইট সাবট্রির হাইট চেক করব এবং দুটির ম্যাক্সিমামে ১ যোগ করব। এটি একটি রিকারসিভ প্রসেস যা এভাবে চলবে যতক্ষণ না ট্রির লাস্ট নোড পাওয়া যায় এবং প্রোগ্রেসিভলি ১ যোগ করে সাব-ট্রিগুলোর হাইট বের করা হবে।
উপরের উদাহরণ এই মেথড দিয়ে সমাধান
ট্রির হাইট বের করতে অর্থাৎ height(3) = max(height(5),height(7)) + 1।
এ জন্য, আমরা ৫ এবং ৭ ভ্যালুর নোডগুলোর হাইট ক্যালকুলেট করব।
height(5) = max(height(1),height(9)) + 1 এবং
height(7) = 1, এর কোনো সাবট্রি নেই।
সারিমিলারলি, height(1) = height(9) = 1
height(5) = max(1,1) +1 = 2
height(3) = max(height(5),height(7)) + 1 = max(2,1) + 1 = 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
