इस समस्या में हमें एक बाइनरी ट्री दिया जाता है। हमारा काम बाइनरी ट्री की न्यूनतम गहराई का पता लगाना है।
बाइनरी ट्री की एक विशेष शर्त है कि प्रत्येक नोड में अधिकतम दो बच्चे हो सकते हैं।
बाइनरी ट्री की न्यूनतम गहराई रूट नोड से किसी भी लीफ नोड के बीच का सबसे छोटा रास्ता है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
आउटपुट
2
समाधान दृष्टिकोण
समस्या का समाधान बाइनरी ट्री को पार करना और ऊंचाइयों को गिनना है। यह प्रत्येक नोड नॉन-लीफ नोड के लिए नोड के चाइल्ड नोड के लिए रिकर्सिवली कॉल करके किया जा सकता है और प्रत्येक लीफ नोड के लिए 1 लौटाया जा सकता है।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
उदाहरण
#include<bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* left, *right;
};
int findMinDepthBT(Node *currentNode) {
if (currentNode == NULL)
return 0;
if (currentNode->left == NULL && currentNode->right == NULL)
return 1;
if (!currentNode->left)
return findMinDepthBT(currentNode->right) + 1;
if (!currentNode->right)
return findMinDepthBT(currentNode->left) + 1;
return min(findMinDepthBT(currentNode->left),
findMinDepthBT(currentNode->right)) + 1;
}
Node *newNode(int data) {
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return (temp);
}
int main() {
Node *root = newNode(5);
root->left = newNode(2);
root->right = newNode(9);
root->left->left = newNode(5);
root->left->right = newNode(1);
root->left->left->left = newNode(7);
root->left->left->right = newNode(3);
cout<<"The minimum depth of binary tree is "<<findMinDepthBT(root);
return 0;
} आउटपुट
The minimum depth of binary tree is 2
यह दृष्टिकोण काफी कुशल है लेकिन हम न्यूनतम गहराई को अधिक प्रभावी ढंग से खोजने के लिए अन्य ट्रैवर्सल तकनीकों का उपयोग कर सकते हैं।
ऐसा ही एक तरीका है लेवल ऑर्डर ट्रैवर्सल का इस्तेमाल करना जिसमें हम ट्री लेवल को लेवल के हिसाब से ट्रैवर्स करते हैं। और हम उस लेवल नंबर को वापस कर देंगे जिसमें हमारा सामना हमारे पहले लीफ नोड से होता है।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
उदाहरण
#include<bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
struct lOrderQueue {
Node *node;
int depth;
};
int findMinDepthBT(Node *root) {
if (root == NULL)
return 0;
queue<lOrderQueue> levelOrder;
lOrderQueue deQueue = {root, 1};
levelOrder.push(deQueue);
while (levelOrder.empty() == false) {
deQueue = levelOrder.front();
levelOrder.pop();
Node *node = deQueue.node;
int depth = deQueue.depth;
if (node->left == NULL && node->right == NULL)
return depth;
if (node->left != NULL) {
deQueue.node = node->left;
deQueue.depth = depth + 1;
levelOrder.push(deQueue);
}
if (node->right != NULL) {
deQueue.node = node->right;
deQueue.depth = depth+1;
levelOrder.push(deQueue);
}
}
return 0;
}
Node* newNode(int data) {
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
int main() {
Node *root = newNode(5);
root->left = newNode(2);
root->right = newNode(9);
root->left->left = newNode(5);
root->left->right = newNode(1);
root->left->left->left = newNode(7);
root->left->left->right = newNode(3);
cout<<"The minimum depth of binary tree is "<<findMinDepthBT(root);
return 0;
} आउटपुट
The minimum depth of binary tree is 2