একটি বাইনারি গাছের ব্যাস প্রতিটি নোডের জন্য (বাম_উচ্চতা + ডান_উচ্চতা + 1)। তাই এই পদ্ধতিতে আমরা প্রতিটি নোডের জন্য (left_height + right_height + 1) গণনা করব এবং ফলাফল আপডেট করব। এখানে সময়ের জটিলতা O(n) থেকে যায়।
আসুন প্রথমে স্ট্রাকটটি সংজ্ঞায়িত করি যা একটি ট্রি নোডকে প্রতিনিধিত্ব করবে যেখানে ডেটা এবং এর বাম এবং ডান নোড চাইল্ড রয়েছে। যদি এটি তৈরি করা প্রথম নোড হয় তবে এটি একটি রুট নোড অন্যথায় একটি চাইল্ড নোড।
struct Node {
int data;
struct Node *leftChild, *rightChild;
}; এরপরে আমরা আমাদের newNode(int data) ফাংশন তৈরি করি যা একটি int মান নেয় এবং নোডের ডেটা মেম্বারকে বরাদ্দ করি। ফাংশন তৈরি করা স্ট্রাকট নোডে পয়েন্টার ফিরিয়ে দেয়। এছাড়াও, নতুন তৈরি নোডের বাম এবং ডান চাইল্ড নাল সেট করা হয়েছে৷
৷struct Node* newNode(int data){
struct Node* newNode = new Node;
newNode->data = data;
newNode->leftChild = newNode->rightChild = NULL;
return (newNode);
} ব্যাস (নোড* রুট) ফাংশন রুট নোড নেয় এবং রুট নোডটি নাল কিনা তা পরীক্ষা করে। তারপরে আমরা INT_MIN মান সহ ans ভেরিয়েবলকে সংজ্ঞায়িত করি। height(root, ans) থেকে রিটার্ন মান height_of_tree ভেরিয়েবলে সংরক্ষণ করা হয়। ফাংশন থেকে উত্তর ফেরত দেওয়া হয়।
int diameter(Node* root){
if (root == NULL)
return 0;
int ans = INT_MIN;
int height_of_tree = height(root, ans);
return ans;
} উচ্চতা (নোড* রুট, int এবং উত্তর) ফাংশনটি রেফারেন্স দ্বারা রুট নোড এবং উত্তর পরিবর্তনশীল নেয়। তারপরে আমরা গাছের প্রতিটি উপবৃক্ষের দৈর্ঘ্য গণনা করার জন্য ইনঅর্ডার ট্রাভার্সাল করি এবং প্রতিটি পুনরাবৃত্ত কলে উত্তরের সর্বোচ্চ মান দ্বিতীয় প্যারামিটার হিসাবে পাস করা হয়। উত্তর হল সর্বাধিক (উত্তর, 1 + বাম_উচ্চতা + ডান_উচ্চতা)।
উদাহরণ
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
