इस समस्या में, हमें एक बाइनरी ट्री दी गई है। हमारा कार्य बाइनरी ट्री की न्यूनतम गहराई ज्ञात करना है।
बाइनरी ट्री की एक विशेष शर्त होती है कि प्रत्येक नोड के अधिकतम दो बच्चे हो सकते हैं।
बाइनरी ट्री की न्यूनतम गहराई रूट नोड से किसी भी लीफ नोड तक का सबसे छोटा पथ होता है।
आइए एक उदाहरण से समझते हैं:
इनपुट
आउटपुट
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
