इस समस्या में, हमें एक बाइनरी ट्री दिया गया है। हमारा कार्य बाइनरी ट्री में सबसे गहरा नोड ज्ञात करना है।
बाइनरी ट्री डेटा स्टोरेज उद्देश्यों के लिए उपयोग की जाने वाली एक विशेष डेटा संरचना है। एक बाइनरी ट्री में एक विशेष शर्त होती है कि प्रत्येक नोड के अधिकतम दो बच्चे हो सकते हैं।
बाइनरी ट्री में सबसे गहरा नोड वह नोड है जो ट्री में अधिकतम संभव ऊंचाई पर है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट :
आउटपुट : 8
समाधान दृष्टिकोण
इस समस्या को हल करने के कई तरीके हो सकते हैं, क्योंकि आपको ऊंचाई ढूंढनी है और ट्री को उस ऊंचाई पर अंतिम नोड तक पार करना है और उसे लौटाना है। सभी समाधान केवल इस सिद्धांत पर आधारित होंगे। यहां, हमने कुछ आशाजनक और अनुकूलित समाधानों पर चर्चा की है।
समस्या का एक सरल समाधान ट्री के इनऑर्डर ट्रैवर्सल का उपयोग करना और एक लेवल मार्क बनाए रखना है, यदि वर्तमान लेवल maxLevel से अधिक है। हम नोड को deepestNode के रूप में आरंभ करेंगे। ट्री के सभी नोड्स को पार करने के बाद, हम deepestNode लौटाएंगे। ट्री के ट्रैवर्सल के लिए, हम पुनरावृत्ति का उपयोग करेंगे।
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम
#include <iostream> using namespace std; struct Node{ int data; struct Node *left, *right; }; Node *newNode(int data){ Node *temp = new Node; temp->data = data; temp->left = temp->right = NULL; return temp; } void findDeepestNodeRec(Node *root, int currentLevel, int &maxLevel, int &deepestNode){ if (root != NULL){ findDeepestNodeRec(root->left, ++currentLevel, maxLevel, deepestNode); if (currentLevel > maxLevel){ deepestNode = root->data; maxLevel = currentLevel; } findDeepestNodeRec(root->right, currentLevel, maxLevel, deepestNode); } } int findDeepestNodeBT(Node *root){ int deepestNode = 0; int maxLevel = 0; findDeepestNodeRec(root, 0, maxLevel, deepestNode); return deepestNode; } int main(){ Node* root = newNode(3); root->left = newNode(5); root->right = newNode(4); root->left->left = newNode(1); root->left->right = newNode(9); root->right->left = newNode(6); root->right->left->right = newNode(8); cout<<"दिए गए बाइनरी ट्री का सबसे गहरा नोड है "<<findDeepestNodeBT(root); return 0; } आउटपुट
दिए गए बाइनरी ट्री का सबसे गहरा नोड है 8
एक अन्य दृष्टिकोण समस्या को हल करने के लिए दिए गए ट्री की ऊंचाई ढूंढना है। और फिर उस नोड को लौटाएं जो ट्री की ऊंचाई के बराबर लेवल पर है।
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम
#include <bits/stdc++.h> using namespace std; struct Node{ int data; struct Node *left, *right; }; Node *newNode(int data){ Node *temp = new Node; temp->data = data; temp->left = temp->right = NULL; return temp; } int calcHeight(Node* root){ if(!root) return 0; int leftHt = calcHeight(root->left) + 1; int rightHt = calcHeight(root->right) + 1; return max(leftHt, rightHt); } void findDeepestNodeBT(Node* root, int levels){ if(!root) return; if(levels == 1) cout << root->data; else if(levels > 1){ findDeepestNodeBT(root->left, levels - 1); findDeepestNodeBT(root->right, levels - 1); } } int main(){ Node* root = newNode(3); root->left = newNode(5); root->right = newNode(4); root->left->left = newNode(1); root->left->right = newNode(9); root->right->left = newNode(6); root->right->left->right = newNode(8); int maxHeight = calcHeight(root); cout<<"बाइनरी ट्री का सबसे गहरा नोड है "; findDeepestNodeBT(root, maxHeight); return 0; } आउटपुट
बाइनरी ट्री का सबसे गहरा नोड है 8
