একটি বাইনারি ট্রির ডায়ামিটার হলো (left_height + right_height + 1) প্রতিটি নোডের জন্য। এই পদ্ধতিতে আমরা প্রতিটি নোডের জন্য (left_height + right_height + 1) ক্যালকুলেট করব এবং রেজাল্ট আপডেট করব। এখানে টাইম কমপ্লেক্সিটি O(n) থাকে।
প্রথমে স্ট্রাক্ট ডিফাইন করি যা ট্রি নোড রিপ্রেজেন্ট করবে যাতে ডেটা এবং এর বাম ও ডান চাইল্ড নোড থাকে। যদি এটি প্রথম নোড হয় তবে এটি রুট নোড হবে অন্যথায় চাইল্ড নোড।
struct Node {
int data;
struct Node *leftChild, *rightChild;
};
পরবর্তীতে newNode(int data) ফাংশন তৈরি করি যা একটি int মান নেয় এবং সেটি নোডের ডেটা মেম্বরে অ্যাসাইন করে। ফাংশনটি তৈরি হওয়া struct Node-এর পয়েন্টার ফেরত দেয়। এছাড়া নতুন নোডের বাম ও ডান চাইল্ড নাল সেট করা হয়।
struct Node* newNode(int data){
struct Node* newNode = new Node;
newNode->data = data;
newNode->leftChild = newNode->rightChild = NULL;
return (newNode);
}
diameter(Node* root) ফাংশন রুট নোড নেয় এবং চেক করে রুট নাল কিনা। তারপর ans ভেরিয়েবল INT_MIN মান দিয়ে ডিক্লেয়ার করা হয়। height(root, ans) থেকে ফেরত আসা মান height_of_tree ভেরিয়েবলে স্টোর করা হয়। ans ফাংশন থেকে ফেরত দেওয়া হয়।
int diameter(Node* root){
if (root == NULL)
return 0;
int ans = INT_MIN;
int height_of_tree = height(root, ans);
return ans;
}
height(Node* root, int& ans) ফাংশন রুট নোড এবং রেফারেন্স হিসেবে ans ভেরিয়েবল নেয়। তারপর ইনঅর্ডার ট্রাভার্সাল করি ট্রির প্রতিটি সাবট্রির দৈর্ঘ্য ক্যালকুলেট করতে এবং প্রতিটি রিকার্সিভ কললে ans-এর ম্যাক্সিমাম মান পাস করা হয়। ans হলো (ans, 1 + left_height + right_height)-এর ম্যাক্স।
উদাহরণ
O(n) মেথডে বাইনারি ট্রির ডায়ামিটার বের করার ইমপ্লিমেন্টেশন:
#include <iostream>
using namespace std;
struct Node {
int data;
Node* leftChild, *rightChild;
};
struct Node* newNode(int data){
struct Node* newNode = new Node;
newNode->data = data;
newNode->leftChild = newNode->rightChild = NULL;
return (newNode);
}
int height(Node* root, int& ans){
if (root == NULL)
return 0;
int left_height = height(root->left, ans);
int right_height = height(root->right, ans);
ans = max(ans, 1 + left_height + right_height);
return 1 + max(left_height, right_height);
}
int diameter(Node* root){
if (root == NULL)
return 0;
int ans = INT_MIN;
int height_of_tree = height(root, ans);
return ans;
}
int main(){
struct Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
printf("Diameter is %d\n", diameter(root));
return 0;
}
আউটপুট
Diameter is 4
