এই সমস্যায়, আমরা একটি বাইনারি গাছ দেওয়া হয়. আমাদের কাজ হল একটি বাইনারি ট্রিতে গভীরতম নোড খুঁজে পাওয়া .
বাইনারি ট্রি হল একটি বিশেষ ডেটা স্ট্রাকচার যা ডেটা স্টোরেজের উদ্দেশ্যে ব্যবহৃত হয়। একটি বাইনারি গাছের একটি বিশেষ শর্ত রয়েছে যে প্রতিটি নোডে সর্বাধিক দুটি শিশু থাকতে পারে৷
একটি বাইনারি গাছের গভীরতম নোড নোড হল গাছের সর্বোচ্চ সম্ভাব্য উচ্চতায়।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট:
আউটপুট:8
সমাধান পদ্ধতি
এই সমস্যাটি সমাধান করার একাধিক উপায় থাকতে পারে, কারণ আপনাকে উচ্চতা খুঁজে বের করতে হবে এবং গাছটিকে উচ্চতায় শেষ নোড পর্যন্ত অতিক্রম করতে হবে এবং এটি ফিরিয়ে দিতে হবে। সমস্ত সমাধান শুধুমাত্র এই নীতির উপর মিথ্যা হবে। এখানে, আমরা কিছু আশাব্যঞ্জক এবং অপ্টিমাইজড সমাধান নিয়ে আলোচনা করেছি৷
৷সমস্যার একটি সহজ সমাধান হল গাছের ইনঅর্ডার ট্রাভার্সাল ব্যবহার করা এবং একটি স্তরের চিহ্ন বজায় রাখা, যদি বর্তমান স্তরটি maxLevel-এর থেকে বেশি হয়। আমরা নোডটিকে 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<<"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
