बाइनरी ट्री का व्यास प्रत्येक नोड के लिए (left_height + right_height + 1) होता है। इसलिए इस विधि में हम प्रत्येक नोड के लिए (left_height + right_height + 1) की गणना करेंगे और परिणाम को अपडेट करेंगे। यहां समय जटिलता O(n) रहती है।
आइए पहले उस स्ट्रक्ट को परिभाषित करें जो एक ट्री नोड को दर्शाता है जिसमें डेटा और इसके बाएं और दाएं चाइल्ड नोड होते हैं। यदि यह बनाया जाने वाला पहला नोड है तो यह रूट नोड है अन्यथा चाइल्ड नोड।
struct Node {
int data;
struct Node *leftChild, *rightChild;
};
इसके बाद हम newNode(int data) फंक्शन बनाते हैं जो एक int मान लेता है और इसे नोड के डेटा सदस्य को असाइन करता है। फंक्शन बने हुए स्ट्रक्ट Node का पॉइंटर वापस करता है। साथ ही, नव निर्मित नोड के बाएं और दाएं चाइल्ड को null पर सेट किया जाता है।
struct Node* newNode(int data){
struct Node* newNode = new Node;
newNode->data = data;
newNode->leftChild = newNode->rightChild = NULL;
return (newNode);
}
diameter(Node* root) फंक्शन रूट नोड लेता है और जांचता है कि रूट नोड null है या नहीं। हम फिर 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->leftChild, ans);
int right_height = height(root->rightChild, 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->leftChild = newNode(2);
root->rightChild = newNode(3);
root->leftChild->leftChild = newNode(4);
root->leftChild->rightChild = newNode(5);
printf("Diameter is %d\n", diameter(root));
return 0;
}
आउटपुट
उपरोक्त कोड निम्नलिखित आउटपुट देगा:
Diameter is 4
