इस समस्या में, हमें एक बाइनरी ट्री दिया गया है। हमारा कार्य दी गई ट्री की अधिकतम गहराई या ऊंचाई खोजने के लिए एक प्रोग्राम लिखना है।
आइए एक उदाहरण से समस्या को समझते हैं,

ट्री की ऊंचाई 3 है।
ट्री की अधिकतम ऊंचाई खोजने के लिए, हम उसके लेफ्ट और राइट सबट्री की ऊंचाई की जांच करेंगे और दोनों के अधिकतम में एक जोड़ देंगे। यह एक रिकर्सिव प्रक्रिया है जो तब तक जारी रहेगी जब तक ट्री का अंतिम नोड नहीं मिल जाता और सब-ट्री की ऊंचाई खोजने के लिए उत्तरोत्तर एक जोड़ा जाता है।
उपरोक्त उदाहरण को इस विधि से हल करना।
ट्री की ऊंचाई यानी height(3) = max(height(5),height(7)) + 1 खोजना।
इसके लिए, हम मान 5 और 7 वाले नोड्स की ऊंचाई की गणना करेंगे।
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।
तो ऊंचाई 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