এই সমস্যায় আমাদের একটি বাইনারি ট্রি এবং প্যারেন্ট পয়েন্টার দেওয়া হয়েছে। আমাদের কাজ হল প্যারেন্ট পয়েন্টার সহ একটি বাইনারি গাছের সঠিক ভাইবোন খুঁজে পাওয়া।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
Node = 3
আউটপুট
7
সমাধান পদ্ধতি
সমস্যার একটি সহজ সমাধান হল নিকটতম পূর্বপুরুষের লিফ নোড খুঁজে বের করা (যা বর্তমান নোড নয় এবং বর্তমান নোডের প্যারেস্টও নয়) যা বর্তমান নোডের সমান স্তরে রয়েছে। এটি উপরে যাওয়ার সময় স্তরগুলি গণনা করে এবং তারপরে নেমে আসার সময় তাদের নীচে গণনা করে করা হয়। এবং তারপর নোড খোঁজা।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *left, *right, *parent;
};
Node* newNode(int item, Node* parent) {
Node* temp = new Node;
temp->data = item;
temp->left = temp->right = NULL;
temp->parent = parent;
return temp;
}
Node* findRightSiblingNodeBT(Node* node, int level) {
if (node == NULL || node->parent == NULL)
return NULL;
while (node->parent->right == node ||
(node->parent->right == NULL && node->parent->left == node)) {
if (node->parent == NULL || node->parent->parent == NULL)
return NULL;
node = node->parent;
level++;
}
node = node->parent->right;
if (node == NULL)
return NULL;
while (level > 0) {
if (node->left != NULL)
node = node->left;
else if (node->right != NULL)
node = node->right;
else
break;
level--;
}
if (level == 0)
return node;
return findRightSiblingNodeBT(node, level);
}
int main(){
Node* root = newNode(4, NULL);
root->left = newNode(2, root);
root->right = newNode(5, root);
root->left->left = newNode(1, root->left);
root->left->left->left = newNode(9, root->left->left);
root->left->left->left->left = newNode(3, root->left->left->left);
root->right->right = newNode(8, root->right);
root->right->right->right = newNode(0, root->right->right);
root->right->right->right->right = newNode(7, root->right->right->right);
Node * currentNode = root->left->left->left->left;
cout<<"The current node is "<<currentNode->data<<endl;
Node* rightSibling = findRightSiblingNodeBT(currentNode, 0);
if (rightSibling)
cout<<"The right sibling of the current node is "<<rightSibling->data;
else
cout<<"No right siblings found!";
return 0;
} আউটপুট
The current node is 3 The right sibling of the current node is 7
