इस समस्या में हमें एक बाइनरी ट्री दिया जाता है। हमारा काम है बाइनरी ट्री में सबसे गहरा नोड ढूंढना ।
बाइनरी ट्री एक विशेष डेटा संरचना है जिसका उपयोग डेटा भंडारण उद्देश्यों के लिए किया जाता है। बाइनरी ट्री की एक विशेष शर्त होती है कि प्रत्येक नोड में अधिकतम दो बच्चे हो सकते हैं।
बाइनरी ट्री में सबसे गहरा नोड वह नोड है जो पेड़ में अधिकतम संभव ऊंचाई पर होता है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट :
आउटपुट :8
समाधान दृष्टिकोण
इस समस्या को हल करने के कई तरीके हो सकते हैं, क्योंकि आपको ऊंचाई खोजने और पेड़ को ऊंचाई पर अंतिम नोड तक ले जाने और उसे वापस करने की आवश्यकता है। सभी समाधान इसी सिद्धांत पर आधारित होंगे। यहां, हमने कुछ आशाजनक और अनुकूलित समाधानों पर चर्चा की है।
समस्या का एक सरल समाधान पेड़ के इनऑर्डर ट्रैवर्सल का उपयोग करना और एक स्तर चिह्न बनाए रखना है, यदि वर्तमान स्तर अधिकतम स्तर से अधिक है। हम नोड को डीपेस्टनोड के रूप में इनिशियलाइज़ करेंगे। पेड़ के सभी नोड्स को पार करने के बाद, हम सबसे गहरा नोड लौटाएंगे। पेड़ के ट्रैवर्सल के लिए, हम रिकर्सन का उपयोग करेंगे।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम
#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<<"The deepest node of the given binary tree is "<<findDeepestNodeBT(root);
return 0;
} आउटपुट
The deepest node of the given binary tree is 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<<"The deepest node of the binary tree is ";
findDeepestNodeBT(root, maxHeight);
return 0;
} आउटपुट
The deepest node of the binary tree is 8